LeetCode Keyboard Row
Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.
Example 1:
Input: ["Hello", "Alaska", "Dad", "Peace"] Output: ["Alaska", "Dad"]Note:
- You may use one character in the keyboard more than once.
- You may assume the input string will only contain letters of alphabet.
给定一个单词数组，问哪些单词可以只由键盘上同一行的字母构成。 简单题，把同一行的字母Hash到同一个值，然后判断单词中不同字母的Hash值是否相同，如果相同则正确，否则不正确。 因为单词只包含大小写字母，所以可以用26长的数组实现Hash功能。代码如下： [cpp] class Solution { private: vector<int> hash; void init() { hash.resize(26); hash[‘q’ – ‘a’] = hash[‘w’ – ‘a’] = hash[‘e’ – ‘a’] = hash[‘r’ – ‘a’] = hash[‘t’ – ‘a’] = hash[‘y’ – ‘a’] = hash[‘u’ – ‘a’] = hash[‘i’ – ‘a’] = hash[‘o’ – ‘a’] = hash[‘p’ – ‘a’] = 1; hash[‘a’ – ‘a’] = hash[‘s’ – ‘a’] = hash[‘d’ – ‘a’] = hash[‘f’ – ‘a’] = hash[‘g’ – ‘a’] = hash[‘h’ – ‘a’] = hash[‘j’ – ‘a’] = hash[‘k’ – ‘a’] = hash[‘l’ – ‘a’] = 2; hash[‘z’ – ‘a’] = hash[‘x’ – ‘a’] = hash[‘c’ – ‘a’] = hash[‘v’ – ‘a’] = hash[‘b’ – ‘a’] = hash[‘n’ – ‘a’] = hash[‘m’ – ‘a’] = 3; } public: vector<string> findWords(vector<string>& words) { init(); vector<string> ans; for (int i = 0; i < words.size(); ++i) { int id = 0; bool good = true; for (int j = 0; j < words[i].size(); ++j) { char c = tolower(words[i][j]); if (id != 0 && hash[c - 'a'] != id) { good = false; break; } id = hash[c - 'a']; } if (good)ans.push_back(words[i]); } return ans; } }; [/cpp] 本代码提交AC，用时0MS。]]>