0748-最短补全词

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

给你一个字符串 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] 由小写英文字母组成

方法一：统计字符出现次数

根据题意，我们先统计 licensePlate 中每个字母的出现次数（忽略大小写），然后遍历 words 中的每个单词，若 26 个字母在该单词中的出现次数均不小于在 licensePlate 中的出现次数，则该单词是一个补全词。返回最短且最靠前的补全词。

[sol1-Python3]
1
2
3
4
class Solution:
    def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
        cnt = Counter(ch.lower() for ch in licensePlate if ch.isalpha())
        return min((word for word in words if not cnt - Counter(word)), key=len)
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    string shortestCompletingWord(string licensePlate, vector<string> &words) {
        array<int, 26> cnt{};
        for (char ch : licensePlate) {
            if (isalpha(ch)) {
                ++cnt[tolower(ch) - 'a'];
            }
        }
        int idx = -1;
        for (int i = 0; i < words.size(); ++i) {
            array<int, 26> c{};
            for (char ch : words[i]) {
                ++c[ch - 'a'];
            }
            bool ok = true;
            for (int j = 0; j < 26; ++j) {
                if (c[j] < cnt[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok && (idx < 0 || words[i].length() < words[idx].length())) {
                idx = i;
            }
        }
        return words[idx];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public String shortestCompletingWord(String licensePlate, String[] words) {
        int[] cnt = new int[26];
        for (int i = 0; i < licensePlate.length(); ++i) {
            char ch = licensePlate.charAt(i);
            if (Character.isLetter(ch)) {
                ++cnt[Character.toLowerCase(ch) - 'a'];
            }
        }
        int idx = -1;
        for (int i = 0; i < words.length; ++i) {
            int[] c = new int[26];
            for (int j = 0; j < words[i].length(); ++j) {
                char ch = words[i].charAt(j);
                ++c[ch - 'a'];
            }
            boolean ok = true;
            for (int j = 0; j < 26; ++j) {
                if (c[j] < cnt[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok && (idx < 0 || words[i].length() < words[idx].length())) {
                idx = i;
            }
        }
        return words[idx];
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public string ShortestCompletingWord(string licensePlate, string[] words) {
        int[] cnt = new int[26];
        foreach (char ch in licensePlate) {
            if (char.IsLetter(ch)) {
                ++cnt[char.ToLower(ch) - 'a'];
            }
        }
        int idx = -1;
        for (int i = 0; i < words.Length; ++i) {
            int[] c = new int[26];
            foreach (char ch in words[i]) {
                ++c[ch - 'a'];
            }
            bool ok = true;
            for (int j = 0; j < 26; ++j) {
                if (c[j] < cnt[j]) {
                    ok = false;
                    break;
                }
            }
            if (ok && (idx < 0 || words[i].Length < words[idx].Length)) {
                idx = i;
            }
        }
        return words[idx];
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func shortestCompletingWord(licensePlate string, words []string) (ans string) {
    cnt := [26]int{}
    for _, ch := range licensePlate {
        if unicode.IsLetter(ch) {
            cnt[unicode.ToLower(ch)-'a']++
        }
    }

next:
    for _, word := range words {
        c := [26]int{}
        for _, ch := range word {
            c[ch-'a']++
        }
        for i := 0; i < 26; i++ {
            if c[i] < cnt[i] {
                continue next
            }
        }
        if ans == "" || len(word) < len(ans) {
            ans = word
        }
    }
    return
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
var shortestCompletingWord = function(licensePlate, words) {
    const cnt = new Array(26).fill(0);
    for (const ch of licensePlate) {
        if (/^[a-zA-Z]+/.test(ch)) {
            ++cnt[ch.toLowerCase().charCodeAt() - 'a'.charCodeAt()];
        }
    }
    let idx = -1;
    for (let i = 0; i < words.length; ++i) {
        const c = Array(26).fill(0);
        for (let j = 0; j < words[i].length; ++j) {
            const ch = words[i][j];
            ++c[ch.charCodeAt() - 'a'.charCodeAt()];
        }
        let ok = true;
        for (let j = 0; j < 26; ++j) {
            if (c[j] < cnt[j]) {
                ok = false;
                break;
            }
        }
        if (ok && (idx < 0 || words[i].length < words[idx].length)) {
            idx = i;
        }
    }
    return words[idx];
};
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
char * shortestCompletingWord(char * licensePlate, char ** words, int wordsSize){
    int cnt[26];
    int n = strlen(licensePlate);
    memset(cnt, 0 ,sizeof(cnt));

    for(int i = 0; i < n; ++i) {
        if (isalpha(licensePlate[i])) {
            ++cnt[tolower(licensePlate[i]) - 'a'];
        }
    }
    int idx = -1;
    int minLen = INT_MAX;
    for (int i = 0; i < wordsSize; ++i) {
        int currLen = strlen(words[i]);
        int c[26];
        memset(c, 0, sizeof(c));
        for (int j = 0; j < currLen; ++j) {
            ++c[words[i][j] - 'a'];
        }
        bool ok = true;
        for (int j = 0; j < 26; ++j) {
            if (c[j] < cnt[j]) {
                ok = false;
                break;
            }
        }
        if (ok && (idx < 0 || currLen < minLen)) {
            minLen = currLen;
            idx = i;
        }
    }
    return words[idx];
}

复杂度分析

  • 时间复杂度：O(N+L+M\cdot |\Sigma|)，其中 N 是字符串 licensePlate 的长度，L 是 words 中的所有字符串的长度之和，M 是 words 数组的长度，|\Sigma| 为字符集合的大小，本题中有 26 个英文字母，即 |\Sigma|=26。

  • 空间复杂度：O(|\Sigma|)。

 Comments
On this page
0748-最短补全词