[LeetCode] 966. Vowel Spellchecker

[grandyang]

Given a wordlist, we want to implement a spellchecker that converts a query word into a correct word.

For a given query word, the spell checker handles two categories of spelling mistakes:

• Capitalization: If the query matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the case in the wordlist.
  • Example: wordlist = ["yellow"], query = "YellOw": correct = "yellow"
  • Example: wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
  • Example: wordlist = ["yellow"], query = "yellow": correct = "yellow"
• Vowel Errors: If after replacing the vowels ('a', 'e', 'i', 'o', 'u') of the query word with any vowel individually, it matches a word in the wordlist (case-insensitive), then the query word is returned with the same case as the match in the wordlist.
  • Example: wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
  • Example: wordlist = ["YellOw"], query = "yeellow": correct = "" (no match)
  • Example: wordlist = ["YellOw"], query = "yllw": correct = "" (no match)

In addition, the spell checker operates under the following precedence rules:

• When the query exactly matches a word in the wordlist (case-sensitive), you should return the same word back.
• When the query matches a word up to capitlization, you should return the first such match in the wordlist.
• When the query matches a word up to vowel errors, you should return the first such match in the wordlist.
• If the query has no matches in the wordlist, you should return the empty string.

Given some queries, return a list of words answer, where answer[i] is the correct word for query = queries[i].

Example 1:

Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]

Note:

• 1 <= wordlist.length <= 5000
• 1 <= queries.length <= 5000
• 1 <= wordlist[i].length <= 7
• 1 <= queries[i].length <= 7
• All strings in wordlist and queries consist only of english letters.

这道题给了一组单词，让实现一个拼写检查器，把查询单词转换成一个正确的单词。这个拼写检查器主要有两种功能，一种是可以忽略大小写，另一种是忽略元音的错误，所谓元音是 a，e，i，o，u，这五个字母。另外题目中还制定了一些其他规则：假如有和查询单词一模一样的单词，考虑大小写，此时应该优先返回。第二个优先级是字母及顺序都一样，但大小写可能不同的，第三个优先级是有元音错误的单词也可以返回，最后都不满足的话返回空串。首先对于第一种情况，返回和查询单词一模一样的单词，很简单，将所有单词放入一个 HashSet 中，这样就可以快速确定一个查询单词是否在原单词数组中出现过。对于第二种情况，做法是将每个单词都转为小写，然后建立小写单词和原单词之间都映射，注意对于转为小写后相同都单词，我们只映射第一个出现该小写状态的单词，后面的不用管。对于第三种情况，对于每个单词，转为小写之后，然后把所有的元音字母用特殊字符替代，比如下划线，然后也是建立这种特殊处理后的状态和原单词之间的映射。当映射都建立好了之后，就可以遍历所有的查询单词了，首先是去 HashSet 中找，若有跟该查询单词一模一样的，直接加入结果 res 中。若没有，则先将查询单词变为小写，然后去第一个 HashMap 中查找，若存在，直接加入结果 res 中。若没有，再把所有的元音变为下划线，去第二个 HashMap 中查找，存在则直接加入结果 res 中。若没有，则将空串加入结果 res 中，参见代码如下：

解法一：

class Solution {
public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        vector<string> res;
        unordered_set<string> st;
        unordered_map<string, string> m1;
        unordered_map<string, string> m2;
        for (int i = 0; i < wordlist.size(); ++i) {
            string word = wordlist[i];
            st.insert(word);
            transform(word.begin(), word.end(), word.begin(), ::tolower);
            if (!m1.count(word)) m1[word] = wordlist[i];
            for (char &c : word) {
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') c = '_';
            }
            if (!m2.count(word)) m2[word] = wordlist[i];
        }
        for (string query : queries) {
            if (st.count(query)) {
                res.push_back(query);
                continue;
            }
            transform(query.begin(), query.end(), query.begin(), ::tolower);
            if (m1.count(query)) {
                res.push_back(m1[query]);
                continue;
            }
            for (char &c : query) {
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') c = '_';
            }
            if (m2.count(query)) {
                res.push_back(m2[query]);
                continue;
            }
            res.push_back("");
        }
        return res;
    }
};

讨论：这里博主不得不吐槽一下 C++ 的STL的功能实在不如 Java 强大，若用 Java 写的话，可以直接调用 toLowerCase() 来转小写，同时可以用 replaceAll() 来快速替换元音，而 C++ 就显得很笨拙了，哎，谁让博主就是用 C++ 刷的顺手呢～

Github 同步地址:

#966

参考资料：

https://leetcode.com/problems/vowel-spellchecker/

https://leetcode.com/problems/vowel-spellchecker/discuss/211189/JavaC%2B%2BPython-Two-HashMap

https://leetcode.com/problems/vowel-spellchecker/discuss/211238/C%2B%2B-Hash-Map-("Yellow"-"_yellow"-"yllw")

LeetCode All in One 题目讲解汇总(持续更新中...)