966. Vowel Spellchecker

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 同步地址:

https://github.com/grandyang/leetcode/issues/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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation