LeetCode 966. 元音拼写检查器（哈希）
LeetCode 966. 元音拼写检查器（哈希）
Michael阿明
发布于 2020-07-13 15:15:54
发布于 2020-07-13 15:15:54
文章被收录于专栏：Michael阿明学习之路
1. 题目
在给定单词列表 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] 得到的正确单词。
示例：
输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
提示：
1 <= wordlist.length <= 5000
1 <= queries.length <= 5000
1 <= wordlist[i].length <= 7
1 <= queries[i].length <= 7
wordlist 和 queries 中的所有字符串仅由英文字母组成。来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/vowel-spellchecker 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
class Solution { //C++
public:
vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
// 元音集合
unordered_set<char> vowel = {'a','e','i','o','u'};
// 原始单词集合
unordered_set<string> words(wordlist.begin(), wordlist.end());
//转成小写后的单词 ---- 第一个出现的原始词
unordered_map<string,string> upper_lower;
//转小写且元音标为* ----- 第一个出现的原始词
unordered_map<string,string> vowel_mask;
string s1, s2;
int i = 0, idx = 0;
for(auto& w : wordlist)
{
words.insert(w);
s1 = s2 = w;
for(i = 0; i < w.size(); i++)
{
if(isupper(s1[i]))
{
s1[i] += 32;//转小写
s2[i] += 32;
}
if(vowel.count(s2[i]))
s2[i]='*';
}
if(!upper_lower.count(s1))
upper_lower[s1] = w;
if(!vowel_mask.count(s2))
vowel_mask[s2] = w;
}
vector<string> ans(queries.size(),"");
for(auto& q : queries)
{
if(words.count(q))
ans[idx] = q;
else
{
s1 = s2 = q;
for(i = 0; i < q.size(); i++)
{
if(isupper(s1[i]))
{
s1[i] += 32;//转小写
s2[i] += 32;
}
if(vowel.count(s2[i]))
s2[i]='*';
}
if(upper_lower.count(s1))
ans[idx] = upper_lower[s1];
else if(vowel_mask.count(s2))
ans[idx] = vowel_mask[s2];
}
idx++;
}
return ans;
}
};144 ms 29.1 MB
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020/06/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
