748. 最短补全词
748. 最短补全词
题目
Given a string licensePlate and an array of strings words, find the shortest completing word in words.
A completing word is a word that contains all the letters in licensePlate. Ignore numbers and spaces in licensePlate, and treat letters as case insensitive. If a letter appears more than once in licensePlate, then it must appear in the word the same number of times or more.
For example, if licensePlate`` = "aBc 12c", then it contains letters 'a', 'b' (ignoring case), and 'c' twice. Possible completing words are "abccdef", "caaacab", and "cbca".
Return _the shortestcompleting word in _words . It is guaranteed an answer exists. If there are multiple shortest completing words, return the first one that occurs in words.
Example 1:
Input: licensePlate = "1s3 PSt", words = ["step","steps","stripe","stepple"]
Output: "steps"
Explanation: licensePlate contains letters 's', 'p', 's' (ignoring case), and 't'.
"step" contains 't' and 'p', but only contains 1 's'.
"steps" contains 't', 'p', and both 's' characters.
"stripe" is missing an 's'.
"stepple" is missing an 's'.
Since "steps" is the only word containing all the letters, that is the answer.
Example 2:
Input: licensePlate = "1s3 456", words = ["looks","pest","stew","show"]
Output: "pest"
Explanation: licensePlate only contains the letter 's'. All the words contain 's', but among these "pest", "stew", and "show" are shortest. The answer is "pest" because it is the word that appears earliest of the 3.
Constraints:
1 <= licensePlate.length <= 7licensePlatecontains digits, letters (uppercase or lowercase), or space' '.1 <= words.length <= 10001 <= words[i].length <= 15words[i]consists of lower case English letters.
题目大意
给你一个字符串 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 <= 7licensePlate由数字、大小写字母或空格' '组成1 <= words.length <= 10001 <= words[i].length <= 15words[i]由小写英文字母组成
解题思路
处理
licensePlate：- 转换为小写。
- 去掉所有非字母字符。
- 统计字母出现的次数，存储在一个字典中。
检查单词是否满足条件：
- 对每个单词进行字母计数。
- 确保每个字母在单词中的出现次数不少于
licensePlate中对应字母的出现次数。
遍历
words：- 对每个单词进行检查，如果满足条件则更新最短补全词。
返回结果：
- 返回满足条件的最短单词。
复杂度分析
时间复杂度：
O(l + n * a)- 构建
licensePlate字符统计表的时间为O(l)，其中l是licensePlate的长度。 - 遍历每个单词并检查的时间为
O(n * a)，其中n是words的长度，a是单词的平均长度。
- 构建
空间复杂度：
O(n)，遍历words数组时，对每个单词生成一个计数表，每个计数表最多需要O(26)空间。
代码
/**
* @param {string} licensePlate
* @param {string[]} words
* @return {string}
*/
var shortestCompletingWord = function (licensePlate, words) {
// 统计单词中每个字母的出现次数
const countLetters = (str) => {
const count = new Map();
for (const char of str) {
if (/[a-z]/.test(char)) {
// 只统计字母
count.set(char, (count.get(char) || 0) + 1);
}
}
return count;
};
const licenseCount = countLetters(licensePlate.toLowerCase());
// 检查单词是否满足条件
const isValid = (word) => {
const wordCount = countLetters(word);
for (const [char, freq] of licenseCount) {
if ((wordCount.get(char) || 0) < freq) return false;
}
return true;
};
let res = null;
for (const word of words) {
if (isValid(word)) {
if (!res || word.length < res.length) {
res = word;
}
}
}
return res;
};