Go语言LeetCode500键盘行题解示例详解

2022-12-30 210阅读 0评论

?=题目描述

原题链接 :

500. 键盘行 - 力扣(leetcode) (LeetCode-cn.com)

给你一个字符串数组 Words ,只返回可以使用在 美式键盘 同一行的字母打印出来的单词。键盘如下图所示。

美式键盘 中:

第一行由字符 "qwertyUIoP" 组成。第二行由字符 "asdfghjkl" 组成。第三行由字符 "zxcvbnm" 组成。

Go语言LeetCode500键盘行题解示例详解

示例 1:

输入:words = ["Hello","Alaska","Dad","Peace"] 输出:["Alaska","Dad"] 

示例 2:

输入:words = ["omk"] 输出:[] 

示例 3:

输入:words = ["adsdf","sfd"] 输出:["adsdf","sfd"] 

提示:

1 <= words.length <= 201 <= words[i].length <= 100words[i] 由英文字母(小写和大写字母)组成

思路分析

审完题就觉得这道题应该不难做,但是绝对很麻烦。毕竟看着就是那种判断来判断去的。初步一看判断数组中每个字符串的每个字符就已经是双层循环了。。还有细节处理,啧啧。

这里其实可以用统一小写的,但是我直接在给定字符串就大小写都算上了,其实我想的是先做出来如果性能不行再优化,但是直接0ms就不优化了。

思路就是判断一个字符串的第一个单词属于哪一行的,接下来照着这行判断,出现这行不存在的直接break。都判断完了没有不是的加到结果集中。

因为一开始不知道结果集多长所以创建的数组和给定数组长度一样,再遍历一遍使得结果集大小正好。

AC 代码

class SolutiON { public string[] findWords(String[] words) { String[] res = new String[words.length]; String fir = "qwertyuiopQWERTYUIOP"; 		String sec = "asdfghjklASDFGHJKL"; 		String tir = "zxcvbnmZXCVBNM"; int k = 0; for(int i = 0;i<words.length;i++){ String temp = ""; for(int j = 0;j<words[i].length();j++){ if(fir.indexOf(words[i].charAt(0))!=-1){ temp = fir; }else if(sec.indexOf(words[i].charAt(0))!=-1){ temp = sec; }else{ temp = tir; } if(temp.indexOf(words[i].charAt(j))==-1){ break; } if(temp.indexOf(words[i].charAt(j))!=-1&&j==words[i].length()-1){ res[k]=words[i]; k++; } } } String[] result = new String[k]; for(int p = 0;p<k;p++){ result[p] = res[p]; } return result; } } 

哈希表判断字符是否出现在某一行中

解题思路

题目很简单,依次判断单词是不是可以在某一行键盘打出来即可。我们先建立每行键盘的hashMap;表示该行出现过的字母。

然后判断目标单词的每个字母是否只出现在每行键盘中,具体做法遍历每个字母,都必须含于某行的hashmap

为了写起来方便:

bool b1 = true; bool b2 = true; bool b3 = true; for (auto c: word) { b1 &= m1[c]; b2 &= m2[c]; b3 &= m3[c]; } if (b1 || b2 || b3) ans.push_back(word); 

三行独立判断,有一个为真,即可在一行内打出来。

代码

class Solution { public: string one = "qwertyuiopQWERTYUIOP"; string two = "asdfghjklASDFGHJKL"; string three = "zxcvbnmZXCVBNM"; unordered_map<char, int> m1,m2,m3; vector<string> findWords(vector<string>& words) { for (auto c: one) { m1[c]++; } for (auto c: two) { m2[c]++; } for (auto c: three) { m3[c]++; } vector<string> ans; for (auto word: words) { bool b1 = true; bool b2 = true; bool b3 = true; for (auto c: word) { b1 &= m1[c]; b2 &= m2[c]; b3 &= m3[c]; }  if (b1 || b2 || b3) ans.push_back(word); } return ans; } }; 

复杂度

时间复杂度: O(N)

空间复杂度: O(N)

以上就是Go语言Leetcode500键盘行题解示例详解的详细内容,更多关于go语言题解键盘行的资料请关注云初冀北其它相关文章!

免责声明
本站提供的资源,都来自网络,版权争议与本站无关,所有内容及软件的文章仅限用于学习和研究目的。不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负,我们不保证内容的长久可用性,通过使用本站内容随之而来的风险与本站无关,您必须在下载后的24个小时之内,从您的电脑/手机中彻底删除上述内容。如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。侵删请致信E-mail:Goliszhou@gmail.com
$

发表评论

表情:
评论列表 (暂无评论,210人围观)

还没有评论,来说两句吧...