随机选择一个尚未讲过的哈希算法相关题目：

哈希算法题目：最短完整词

题目描述
给定一个字符串 licensePlate 和一个字符串数组 words。licensePlate 中包含一些字母（可能大小写都有）和数字以及空格，我们只关心其中的字母（不区分大小写）。我们需要在 words 数组中找到这样一个单词：它包含 licensePlate 中所有字母（字母可能出现多次，我们要求单词中对应字母的数量至少为 licensePlate 中该字母的数量），并且是 最短 的。如果有多个最短的完整词，返回其中 最早出现 的一个。如果没有这样的单词，返回空字符串。

示例 1
输入：licensePlate = "1s3 PSt", words = ["step", "steps", "stripe", "stepple"]
输出："steps"
解释：licensePlate 中的字母是 's'、'p'、's'、't'（忽略大小写，注意有两个 's'）。单词 "step" 只包含一个 's'，所以不够。单词 "steps" 包含两个 's' 并且包含 'p'、't'，且长度最短。单词 "stripe" 和 "stepple" 虽然也满足条件，但比 "steps" 长。

示例 2
输入：licensePlate = "1s3 456", words = ["looks", "pest", "stew", "show"]
输出："pest"
解释：licensePlate 中的字母是 's'。所有单词都包含 's'，但 "pest" 最短。

解题过程循序渐进讲解

步骤 1：理解并提炼核心需求

1. 从 licensePlate 中提取所有字母（a-z, A-Z），忽略数字和空格，并将所有字母转换为小写（或大写）以统一处理。
2. 统计这些字母的出现频率，得到一个“字符需求频率表”（类似哈希表计数）。
3. 遍历 words 数组中的每个单词，检查它是否满足：单词中每个字母的出现次数 ≥ 需求频率表中对应字母的出现次数。
4. 在所有满足条件的单词中，找到长度最短的那个；如果多个单词长度相同，取在 words 中下标最小的那个（即最早出现的）。
5. 如果没有单词满足，返回空字符串 ""。

步骤 2：设计数据结构和算法

• 我们需要一个高效的数据结构来存储和比较字母频率。这里适合用 数组哈希表（因为字母只有 26 个，可以用长度为 26 的数组表示频率）。
• 算法步骤：
  a. 预处理 licensePlate，得到需求频率数组 need[26]。
  b. 遍历 words，对每个单词统计其字母频率数组 wordCount[26]。
  c. 比较 wordCount 是否“覆盖” need（即每个字母上 wordCount[i] >= need[i]）。
  d. 记录满足条件的最短单词。

步骤 3：具体实现细节

3.1 预处理 licensePlate

• 遍历 licensePlate 的每个字符：
  • 如果字符是字母（'a' <= c <= 'z' 或 'A' <= c <= 'Z'），将其转换为小写，然后映射到 0-25 的索引（例如 c - 'a'），并在 need 数组对应位置计数加 1。
• 这样我们就得到了需求频率数组 need。

3.2 遍历 words 并检查每个单词

• 对每个单词 word：
  • 初始化一个长度为 26 的数组 wordCount，所有元素为 0。
  • 遍历 word 的每个字母（都是小写字母，但为保险可以转换为小写），在 wordCount 中对应位置计数加 1。
  • 比较 wordCount 和 need：检查所有 26 个字母，如果存在某个字母 i 使得 wordCount[i] < need[i]，则该单词不满足条件；否则满足。

3.3 记录最短且最早出现的单词

• 维护两个变量：shortestLength 初始化为一个很大的数（如 Integer.MAX_VALUE），shortestWord 初始化为空字符串 ""。
• 当找到一个满足条件的单词时：
  • 如果它的长度 < shortestLength，更新 shortestLength 和 shortestWord 为当前单词。
  • 如果它的长度 == shortestLength，不更新（因为我们要最早出现的，而遍历顺序就是从前往后，所以第一个遇到的最短单词就是最早出现的）。
• 遍历结束后，返回 shortestWord。

步骤 4：示例推演
以示例 1 为例：
licensePlate = "1s3 PSt" → 提取字母：'s', 'p', 's', 't'（小写） → need: s:2, p:1, t:1，其他字母为 0。
words = ["step", "steps", "stripe", "stepple"]

• "step": 频率 s:1, t:1, e:1, p:1 → s 只有 1 个，小于 need 中的 2，不满足。
• "steps": 频率 s:2, t:1, e:1, p:1 → 满足所有条件（s≥2, t≥1, p≥1），长度为 5，记录为当前最短。
• "stripe": 频率 s:1, t:1, r:1, i:1, p:1, e:1 → s 只有 1 个，不满足。
• "stepple": 频率 s:1, t:1, e:2, p:2, l:1 → s 只有 1 个，不满足。
  最终返回 "steps"。

步骤 5：复杂度分析

• 时间复杂度：O(N * (L + 26))，其中 N 是 words 的长度，L 是单词的平均长度。因为每个单词遍历一次统计频率（O(L)），再比较 26 个字母（O(26)）。
• 空间复杂度：O(1)，因为 need 和 wordCount 都是固定大小为 26 的数组。

步骤 6：边界情况考虑

• licensePlate 可能没有字母 → need 全 0，那么任何单词都满足条件，返回最短单词（即 words 中长度最短且最早出现的）。
• words 可能为空 → 返回空字符串。
• 单词中字母均为小写，但 licensePlate 可能有大写 → 统一转换为小写处理。
• 多个单词长度相同且都满足条件 → 取第一个遇到的。

步骤 7：代码框架（伪代码）

function shortestCompletingWord(licensePlate, words):
    need = array of size 26, filled with 0
    for each char c in licensePlate:
        if c is a letter:
            lower = toLowerCase(c)
            need[lower - 'a']++
    
    shortestLength = INF
    shortestWord = ""
    
    for each word in words:
        wordCount = array of size 26, filled with 0
        for each char c in word:
            wordCount[c - 'a']++  // 假设 word 中字母都是小写
        // 检查是否覆盖 need
        cover = true
        for i from 0 to 25:
            if wordCount[i] < need[i]:
                cover = false
                break
        if cover and word.length < shortestLength:
            shortestLength = word.length
            shortestWord = word
    
    return shortestWord

总结
这道题本质上是字母频率的包含关系判断，利用固定大小的数组作为哈希表来统计频率，然后进行逐个字母的比较。关键点在于理解“完整词”的定义（即单词的字母频率必须完全覆盖 licensePlate 中字母的频率），以及最短和最早出现的优先级处理。