前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 966. 元音拼写检查器(哈希)

LeetCode 966. 元音拼写检查器(哈希)

作者头像
Michael阿明
发布2020-07-13 15:15:54
5400
发布2020-07-13 15:15:54
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

在给定单词列表 wordlist 的情况下,我们希望实现一个拼写检查器,将查询单词转换为正确的单词。

对于给定的查询单词 query,拼写检查器将会处理两类拼写错误:

  • 大小写:如果查询匹配单词列表中的某个单词(不区分大小写),则返回的正确单词与单词列表中的大小写相同。
代码语言:javascript
复制
例如:wordlist = ["yellow"], query = "YellOw": correct = "yellow"
例如:wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
例如:wordlist = ["yellow"], query = "yellow": correct = "yellow"
  • 元音错误:如果在将查询单词中的元音(‘a’、‘e’、‘i’、‘o’、‘u’)分别替换为任何元音后,能与单词列表中的单词匹配(不区分大小写),则返回的正确单词与单词列表中的匹配项大小写相同。
代码语言:javascript
复制
例如:wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
例如:wordlist = ["YellOw"], query = "yeellow": correct = "" (无匹配项)
例如:wordlist = ["YellOw"], query = "yllw": correct = "" (无匹配项)

此外,拼写检查器还按照以下优先级规则操作:

  • 当查询完全匹配单词列表中的某个单词(区分大小写)时,应返回相同的单词。
  • 当查询匹配到大小写问题的单词时,您应该返回单词列表中的第一个这样的匹配项。
  • 当查询匹配到元音错误的单词时,您应该返回单词列表中的第一个这样的匹配项。
  • 如果该查询在单词列表中没有匹配项,则应返回空字符串。

给出一些查询 queries,返回一个单词列表 answer,其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。

代码语言:javascript
复制
示例:
输入: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. 解题

代码语言:javascript
复制
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 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档