500. 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.

思路:(借鉴别人的)利用掩码(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;
    }
};