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:
Input: ["Hello", "Alaska", "Dad", "Peace"] Output: ["Alaska", "Dad"]
Note:
Approach #1: C++.
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> ans;
vector<unordered_set<char>> temp = {
{‘q‘, ‘w‘, ‘e‘, ‘r‘, ‘t‘, ‘y‘,‘u‘, ‘i‘, ‘o‘, ‘p‘},
{‘a‘, ‘s‘, ‘d‘, ‘f‘, ‘g‘, ‘h‘, ‘j‘, ‘k‘, ‘l‘},
{‘z‘, ‘x‘, ‘c‘, ‘v‘, ‘b‘, ‘n‘, ‘m‘}
};
int size = words.size();
for (int i = 0; i < size; ++i) {
int flag1 = -1;
bool ant = false;
int len = words[i].length();
for (int j = 0; j < len; ++j) {
int flag2 = flag1;
if (words[i][j] > ‘z‘) words[i][j] -= 65;
if (temp[0].count(words[i][j])) flag1 = 0;
if (temp[1].count(words[i][j])) flag1 = 1;
if (temp[2].count(words[i][j])) flag1 = 2;
if (flag2 >= 0 && flag1 != flag2) {
ant = true;
break;
}
}
if (!ant) ans.push_back(words[i]);
}
return ans;
}
};
Approach #2: Java.
class Solution {
public String[] findWords(String[] words) {
String[] strs = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
Map<Character, Integer> map = new HashMap<>();
for (int i = 0; i < strs.length; ++i) {
for (char c: strs[i].toCharArray()) {
map.put(c, i);
}
}
List<String> res = new LinkedList<>();
for (String w : words) {
if (w.equals("")) continue;
int index = map.get(w.toUpperCase().charAt(0));
for (char c : w.toUpperCase().toCharArray()) {
if (map.get(c) != index) {
index = -1;
break;
}
}
if (index != -1) res.add(w);
}
return res.toArray(new String[0]);
}
}
Approach #3: Python.
class Solution(object):
def findWords(self, words):
"""
:type words: List[str]
:rtype: List[str]
"""
line1, line2, line3 = set("qwertyuiop"), set("asdfghjkl"), set("zxcvbnm")
ret = []
for word in words:
w = set(word.lower())
if w.issubset(line1) or w.issubset(line2) or w.issubset(line3):
ret.append(word)
return ret
Analysis:
In the approach one, I use a vector<unordered_set<char>> to contion the keyboard row. Then checking the word‘s characters is only be contioned in one keyboard row. I use tow flags with flag1 and flag2 to mark the previous character and the current character, if they are same with each other always, we can push it to the return vector.
原文：https://www.cnblogs.com/ruruozhenhao/p/9981358.html