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.
思路:(借鉴别人的)利用掩码(mask),定义第一行“QWERTYUIOP”为1(001),第二行(“ASDFGHJKL”) 为2(010),第三行 (“ZXCVBNM”)为4(100).对每个word的每个字符,以7(111)为初始值进行与操作(AND).如果每行都在同一行,则最终结果为1,2或4.如果其中有字符来自不同行,则最终结果为0.
这样比较直观:
001 --> 1
010 --> 2
100 --> 4
以上任两个二进制串进行与操作,其结果都为0,而其中每个与自身与操作,结果不为0.
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<int> dict(26); //将"A-Z"映射到0~25
vector<string> rows = {"QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM"};
for (int i = 0; i < rows.size(); i++) {
for (auto c : rows[i]) dict[c-'A'] = 1 << i; //第一行字符为值为1,第二行为2,第三行为4.
}
vector<string> res;
for (auto w : words) {
int r = 7;
for (char c : w) {
r &= dict[toupper(c)-'A']; //将c转换为大写,再减去'A'映射到dict
if (r == 0) break; //若r为0则不符合条件,跳出本层循环
}
if (r) res.push_back(w);
}
return res;
}
};
