元音拼写检查器

标签: 数组哈希表字符串

难度: Medium

在给定单词列表 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] 只包含英文字母

Submission

运行时间: 68 ms

内存: 18.8 MB

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def f(w):
            t = []
            for c in w:
                t.append("*" if c in "aeiou" else c)
            return "".join(t)

        s = set(wordlist)
        low, pat = {}, {}
        for w in wordlist:
            t = w.lower()
            low.setdefault(t, w)
            pat.setdefault(f(t), w)

        ans = []
        for q in queries:
            if q in s:
                ans.append(q)
                continue
            q = q.lower()
            if q in low:
                ans.append(low[q])
                continue
            q = f(q)
            if q in pat:
                ans.append(pat[q])
                continue
            ans.append("")
        return ans

Explain

该题解利用了哈希表来优化拼写检查器的查询速度。首先，创建了三种映射： 1. 原始单词列表的集合's'，用于检查完全匹配的情况（区分大小写）。 2. 'low'哈希表，将单词列表中的每个单词转换为小写，并存储第一个出现的单词，用于处理大小写错误。 3. 'pat'哈希表，使用一个辅助函数f将单词中的元音替换为'*'，然后转为小写，这样可以处理元音错误的情况。对于每个查询，程序首先检查完全匹配，然后是大小写错误，接着是元音错误，如果都不匹配，则返回空字符串。

时间复杂度: O(n*k + m)

空间复杂度: O(n)

class Solution:
    def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
        def f(w):
            # 将单词中的所有元音替换为'*'
            t = []
            for c in w:
                t.append("*" if c in "aeiou" else c)
            return "".join(t)

        # 创建原始单词的集合
        s = set(wordlist)
        low, pat = {}, {}
        # 建立大小写不敏感和元音替换后的哈希表
        for w in wordlist:
            t = w.lower()
            low.setdefault(t, w)
            pat.setdefault(f(t), w)

        ans = []
        # 对每个查询进行检查
        for q in queries:
            if q in s:
                ans.append(q)
                continue
            q = q.lower()
            if q in low:
                ans.append(low[q])
                continue
            q = f(q)
            if q in pat:
                ans.append(pat[q])
                continue
            ans.append("")
        return ans

Explore

在创建哈希表`low`时，对于每个转换为小写的单词，我使用了`setdefault`方法。这个方法会检查哈希表中是否已经存在该键（小写单词），如果不存在，它会将键和对应的原始单词存入哈希表。因此，第一次遇到的单词版本会被存储，并在后续的查询中被返回，即使后面有相同的小写单词出现，它们也不会覆盖已存储的值。

将元音替换为特定字符'*'而不是删除，是为了保留单词的长度和结构，使得替换后的模式能更好地代表原单词的结构特征，从而更有效地处理元音错误。选择'*'作为替代字符是因为它不太可能在正常的单词中出现，从而避免混淆。使用其他字符亦可，但关键是要保证该字符在一般文本中不常见。

在构建哈希表`pat`时，我同样使用了`setdefault`方法。这意味着如果多个不同的单词在元音替换后形成了相同的模式，哈希表中只会保留第一次遇到的单词。这种方法确保了查询结果的一致性，即使存在多个可能的匹配项，也总是返回列表中最先出现的那个单词。

该算法主要依赖于哈希表来存储数据，其查询和更新操作的时间复杂度通常为O(1)。因此，算法在处理大规模数据时在时间效率上表现良好。然而，如果单词列表极长，可能会造成哈希表占用大量内存。特别是对于`pat`哈希表，如果单词列表中的单词变化多样，替换元音后的模式数量也会很大，可能导致内存使用增加。在极端情况下，这可能导致内存不足，特别是在内存有限的环境中。