LeetCode 题解工作台
最短补全词
给你一个字符串 licensePlate 和一个字符串数组 words ，请你找出 words 中的 最短补全词 。 补全词 是一个包含 licensePlate 中所有字母的单词。 忽略 licensePlate 中的 数字和空格 。 不区分大小写 。如果某个字母在 licensePlate 中出…
3
题型
6
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
我们先用哈希表或者一个长度为 的数组 统计字符串 `licensePlate` 中每个字母出现的次数，注意这里我们统一将字母转换为小写进行计数。 然后，我们遍历数组 `words` 中的每个单词 ，如果单词 的长度比答案 的长度长，那么我们直接跳过该单词。否则，我们再用哈希表或者一个长度为 的数组 统计单词 中每个字母出现的次数。如果对于任意一个字母， 中该字母出现的次数小于 中该…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个字符串 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 中每个字母出现的次数，注意这里我们统一将字母转换为小写进行计数。
然后，我们遍历数组 words 中的每个单词 ，如果单词 的长度比答案 的长度长，那么我们直接跳过该单词。否则，我们再用哈希表或者一个长度为 的数组 统计单词 中每个字母出现的次数。如果对于任意一个字母， 中该字母出现的次数小于 中该字母出现的次数，那么我们也可以直接跳过该单词。否则，我们就找到了一个满足条件的单词，我们更新答案 为当前单词 。
时间复杂度 ，空间复杂度 ，其中 是数组 words 的长度，而 是字符集，这里字符集为所有小写字母，因此 。
class Solution:
def shortestCompletingWord(self, licensePlate: str, words: List[str]) -> str:
cnt = Counter(c.lower() for c in licensePlate if c.isalpha())
ans = None
for w in words:
if ans and len(w) >= len(ans):
continue
t = Counter(w)
if all(v <= t[c] for c, v in cnt.items()):
ans = w
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate effectively counts letter frequencies in both the license plate and words.
- question_mark
The candidate optimizes the solution by focusing on the shortest word after filtering.
- question_mark
The candidate handles edge cases such as multiple matches or no match gracefully.
常见陷阱
外企场景- error
Ignoring letter frequencies and only checking for presence rather than count.
- error
Not converting letters to lowercase, which could lead to incorrect comparisons.
- error
Failing to consider spaces and numbers in the license plate properly.
进阶变体
外企场景- arrow_right_alt
Modify the problem to consider only words with exactly the same length as the shortest word.
- arrow_right_alt
Consider a variant where the words are in sorted order and the first valid word should be returned.
- arrow_right_alt
Change the problem to find the longest word that matches the license plate.