500. Keyboard Row.md

500. Keyboard Row

思路

题目意思就是给定一个字符串，若字符串中的每个字母来自键盘上的同一行，则输出。
我们可以将字母按照键盘布局分类，从上到下分别为0、1、2类。对于每个字符串，遍历一遍，若属于同一类则可输出。
时间复杂度O(n)

C++

class Solution {
private:
    int count_hash_index(char c){
        if(c >= 'a' && c <= 'z') return int(c - 'a');
        return int(c - 'A');
    }
public:
    vector<string> findWords(vector<string>& words) {
        //              a b c d e f g h i j k l m n o p q r s t u v w x y z
        int hash[26] = {1,2,2,1,0,1,1,1,0,1,1,1,2,2,0,0,0,0,1,0,0,2,0,2,0,2};
        vector<string>res;
        int i;
        for(string str: words){
            for(i = 1; i < str.size(); i++){
                if(hash[count_hash_index(str[i])] != hash[count_hash_index(str[i - 1])]) break;
            }
            if(i == str.size()) res.push_back(str); // 正常退出，则所有字母属于同类
        }
        return res;
    }
};