题目描述

在给定单词列表 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 = “” （无匹配项）

(2个哈希表存)

规则①放到cap里
规则②放到vowel里
每次询问query，检查是否在原数据中(words)，检查是否cap里有匹配，检查是否在vowel里有匹配，
否则返回""

C++ 代码

 vector<string> spellchecker(vector<string>& wordlist, vector<string> queries) {
        unordered_set<string> words(wordlist.begin(), wordlist.end());
        unordered_map<string, string> cap, vowel;
        for (string w : wordlist) {
            string lower = tolow(w), devowel = todev(w);
            cap.insert({lower, w});
            vowel.insert({devowel, w});
        }
        for (int i = 0; i < queries.size(); ++i) {
            if (words.count(queries[i])) continue;
            string lower = tolow(queries[i]), devowel = todev(queries[i]);
            if (cap.count(lower)) {
                queries[i] = cap[lower];
            } else if (vowel.count(devowel)) {
                queries[i] = vowel[devowel];
            } else {
                queries[i] = "";
            }
        }
        return queries;
    }

    string tolow(string w) {
        for (auto & c: w)
            c = tolower(c);
        return w;
    }

    string todev(string w) {
        w = tolow(w);
        for (auto & c: w)
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
                c = '#';
        return w;
    }

算法2

Python3 代码

def spellchecker(self, wordlist: List[str], queries: List[str]) -> List[str]:
    words = {a: a for a in wordlist}
    cap = {a.lower(): a for a in wordlist[::-1]} # 注: ::-1 使得第一个匹配的数会覆盖其他匹配
    vowel = {re.sub("[aeiou]", '#', a.lower()): a for a in wordlist[::-1]}
    return [words.get(a) or cap.get(a.lower()) or vowel.get(re.sub("[aeiou]",'#', a.lower()), "") for a in queries]