题目

在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：

• 大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
  • 例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • 例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • 例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"
• 元音错误：如果在将查询单词中的元音 ('a', 'e', 'i', 'o', 'u')  分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
  • 例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • 例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
  • 例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）

此外，拼写检查器还按照以下优先级规则操作：

• 当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
• 当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
• 如果该查询在单词列表中没有匹配项，则应返回空字符串。

给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i]得到的正确单词。

示例 1：

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"] 输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

示例 2:

输入：wordlist = ["yellow"], queries = ["YellOw"] 输出：["yellow"]

提示：

• 1 <= wordlist.length, queries.length <= 5000
• 1 <= wordlist[i].length, queries[i].length <= 7
• wordlist[i] 和 queries[i] 只包含英文字母

解题思路

这道题的难点和关键点有三个：

1. 三种不同的匹配规则：完全匹配、大小写匹配、元音匹配。
2. 严格的优先级：必须先检查“完全匹配”，再检查“大小写”，最后检查“元音”。一旦在高优先级找到匹配，就绝不能再用低优先级的规则去覆盖它。
3. 性能要求：wordlist 和 queries 的长度可能很大，使用双重循环（一个 query 遍历一遍 wordlist）的暴力解法一定会超时。

为了避免每次查询都遍历整个 wordlist，我们可以预先处理 wordlist，将其信息存储在可以进行快速查找的数据结构中。哈希表 (std::unordered_map / std::unordered_set) 是这个场景下的完美工具，因为它能提供平均 O(1) 的查找速度。

第一步：预处理 (Preprocessing)

遍历一遍 wordlist，构建三个查找工具，分别对应三种匹配规则：

1. 为“完全匹配”准备：
   • 工具：一个 unordered_set<string>，我们叫它 exact_words。
   • 作用：将 wordlist 中所有单词原封不动地放进去。之后要判断一个 query 是否完全匹配，只需要在 set 中查找一下，时间是 O(1)。
2. 为“大小写匹配”准备：
   • 工具：一个 unordered_map<string, string>，我们叫它 case_insensitive_map。
   • 作用：键是单词的小写形式，值是它在 wordlist 中的原始形式。
   • 关键细节：题目要求返回第一个匹配项。所以，当我们遍历 wordlist 构建这个 map 时，只有当一个小写键不存在时，我们才将它和对应的原始单词存入。如果键已存在，就跳过，这样可以保证存入的始终是 wordlist 中最先出现的那个。
3. 为“元音匹配”准备：
   • 工具：另一个 unordered_map<string, string>，我们叫它 vowel_error_map。
   • 作用：键是单词的“元音模糊”形式（即转成小写，再把所有元音替换成一个通用占位符，如 '*'），值是它的原始形式。
   • 关键细节：同样，只存入键不存在的词，以保证“第一个匹配项”的规则。

第二步：查询 (Querying)

现在我们有了三个强大的“数据库”，对于每一个 query，我们严格按照优先级顺序进行查找：

1. 在 exact_words 中查找 query。如果找到了，它就是答案，立即处理下一个 query。
2. 如果上一步没找到，将 query 转为小写，在 case_insensitive_map 中查找。如果找到了，对应的值就是答案，立即处理下一个 query。
3. 如果上一步还没找到，将 query 转为“元音模糊”形式，在 vowel_error_map 中查找。如果找到了，对应的值就是答案，立即处理下一个 query。
4. 如果都找不到，答案就是空字符串 ""。

时间复杂度

总时间复杂度是 $O((M+N)⋅L)$

其中：

• M 是 wordlist 的长度。
• N 是 queries 的长度。
• L 是单词的平均长度。

这个复杂度主要来自两个独立的部分：

1. 预处理阶段:
   • 我们遍历 wordlist 一次，其中有 M 个单词。
   • 对于每个单词，我们需要执行小写转换、元音模糊化处理以及哈希表的插入操作。这些操作的时间都与单词的长度 L 成正比（因为需要遍历字符串并计算哈希值）。
   • 所以，这个阶段的复杂度是 $O(M⋅L)$。
2. 查询阶段:
   • 我们遍历 queries 一次，其中有 N 个查询词。
   • 对于每个查询词，我们最多执行三次查找操作（在 set 和两个 map 中）。每次查找，同样需要对字符串进行转换和计算哈希值，时间也与单词长度 L 成正比。
   • 所以，这个阶段的复杂度是 $O(N⋅L)$。

将这两个阶段相加，总的时间复杂度就是 $O(M⋅L+N⋅L)$，可以合并写为 $O((M+N)⋅L)$。

这个方法的空间复杂度也是 $O((M+N)⋅L)$，因为它需要额外的哈希表来存储预处理后的数据，是典型的“空间换时间”策略。