carloscn
commented
1 year ago 问题分析
C语言版本
static int32_t is_contains(const char *in_str, const char *pat, bool *result)
{
int32_t ret = 0;
char *buffer = NULL;
size_t buffer_len;
size_t pat_len;
size_t i = 0, j = 0;
UTILS_CHECK_PTR(in_str);
UTILS_CHECK_PTR(pat);
UTILS_CHECK_PTR(result);
UTILS_CHECK_LEN(buffer_len = strlen(in_str));
UTILS_CHECK_LEN(pat_len = strlen(pat));
buffer = (char *)calloc(sizeof(char), buffer_len + 1);
if (buffer == NULL) {
return false;
}
strcpy(buffer, in_str);
ret = utils_sort_char_array(buffer, buffer_len, ORDER_BY_ASCEND);
UTILS_CHECK_RET(ret);
while (j < buffer_len) {
if (buffer[j] == pat[i]) {
i ++;
}
j ++;
if (i == pat_len) {
*result = true;
goto finish;
}
}
*result = false;
finish:
UTILS_SAFE_FREE(buffer);
return ret;
}
static int32_t shorest_word(STRLIST_T *strlist, const char *pat, size_t *index)
{
int32_t ret = 0;
char *pat_buffer = NULL;
size_t strlist_len = 0;
size_t pat_len = 0;
size_t min_len = ~0;
size_t len = 0;
size_t i = 0;
size_t j = 0;
bool rs = false;
char *str = NULL;
UTILS_CHECK_PTR(strlist);
UTILS_CHECK_PTR(pat);
UTILS_CHECK_PTR(index);
UTILS_CHECK_LEN(strlist_len = strlist_get_size(strlist));
UTILS_CHECK_LEN(pat_len = strlen(pat));
pat_buffer = (char *)calloc(sizeof(char), pat_len + 1);
UTILS_CHECK_PTR(pat_buffer);
strcpy(pat_buffer, pat);
ret = utils_str_filter_letter(pat_buffer);
UTILS_CHECK_RET(ret);
LOG("the buffer is %s\n", pat_buffer);
pat_len = strlen(pat_buffer);
ret = utils_str_to_lowercase(pat_buffer);
UTILS_CHECK_RET(ret);
LOG("the buffer is %s\n", pat_buffer);
ret = utils_sort_char_array(pat_buffer, pat_len, ORDER_BY_ASCEND);
UTILS_CHECK_RET(ret);
LOG("the buffer is %s\n", pat_buffer);
for (i = 0; i < strlist_len; i ++) {
str = strlist_get_str_at(strlist, i);
ret = is_contains(str, pat_buffer, &rs);
UTILS_CHECK_RET(ret);
if (true == rs) {
len = strlen(str);
if (min_len > len) {
min_len = len;
*index = i;
}
}
}
finish:
UTILS_SAFE_FREE(pat_buffer);
return ret;
}Rust版本
use core::str::Chars;
fn is_contains(in_str:&str, pat_str:&str) -> bool
{
let mut in_buffer:String = String::from(in_str);
let mut pat_buffer:String = String::from(pat_str);
let in_len:usize = in_str.len();
let pat_len:usize;
let mut i:usize = 0;
let mut j:usize = 0;
utils::str::sort_by_ascend(&mut in_buffer);
utils::str::to_lowercase(&mut pat_buffer);
utils::str::filter_letter(&mut pat_buffer);
utils::str::sort_by_ascend(&mut pat_buffer);
let in_char:Vec<char> = in_buffer.chars().into_iter().collect();
let pat_char:Vec<char> = pat_buffer.chars().into_iter().collect();
println!("pat is {:?}", in_char);
println!("in is {:?}", pat_char);
pat_len = pat_char.len();
while j < in_len {
if in_char[j] == pat_char[i] {
i += 1;
}
j += 1;
if i == pat_len {
return true;
}
}
return false;
}
fn shortest_word(str_vec:&Vec<String>, pat:String) -> Result<String, &'static str>
{
let mut i:usize = 0;
let v_len = str_vec.len();
let mut min_len:usize = 0xfffffff;
let mut len:usize = 0;
let mut index:usize = 0;
while i < v_len {
let ret = is_contains(&str_vec[i], &pat);
if true == ret {
println!("found {}", str_vec[i]);
len = str_vec[i].len();
if min_len > len {
min_len = len;
index = i;
}
}
i += 1;
}
println!("the index is {index}");
return Ok(str_vec[index].clone());
}
问题描述
给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。
补全词 是一个包含 licensePlate 中所有字母的单词。忽略 licensePlate 中的 数字和空格 。不区分大小写。如果某个字母在 licensePlate 中出现不止一次，那么该字母在补全词中的出现次数应当一致或者更多。
例如：licensePlate = "aBc 12c"，那么它的补全词应当包含字母 'a'、'b' （忽略大写）和两个 'c' 。可能的 补全词 有 "abccdef"、"caaacab" 以及 "cbca" 。
请返回 words 中的 最短补全词 。题目数据保证一定存在一个最短补全词。当有多个单词都符合最短补全词的匹配条件时取 words 中 第一个 出现的那个。
示例 1：
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"] 输出："steps" 解释：最短补全词应该包括 "s"、"p"、"s"（忽略大小写） 以及 "t"。 "step" 包含 "t"、"p"，但只包含一个 "s"，所以它不符合条件。 "steps" 包含 "t"、"p" 和两个 "s"。 "stripe" 缺一个 "s"。 "stepple" 缺一个 "s"。 因此，"steps" 是唯一一个包含所有字母的单词，也是本例的答案。 示例 2：
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"] 输出："pest" 解释：licensePlate 只包含字母 "s" 。所有的单词都包含字母 "s" ，其中 "pest"、"stew"、和 "show" 三者最短。答案是 "pest" ，因为它是三个单词中在 words 里最靠前的那个。
提示：
1 <= licensePlate.length <= 7 licensePlate 由数字、大小写字母或空格 ' ' 组成 1 <= words.length <= 1000 1 <= words[i].length <= 15 words[i] 由小写英文字母组成
来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/shortest-completing-word