[leetcode]: 500. Keyboard Row

快来打我* 2022-06-16 00:42 143阅读 0赞

**1.题目描述**  
Given a List of words, return the words that can be typed using letters of alphabet on only one row’s of American keyboard  
Example 1:  
Input: \[“Hello”, “Alaska”, “Dad”, “Peace”\]  
Output: \[“Alaska”, “Dad”\]  
翻译：给一个单词列表，输出所有字母均在同一行的单词。  
**2.分析**  
输入只有字母，所以将键盘分为三行。  
第一行：【’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’】  
要查找一个单词中所有字母是否在同一行，有两种方式：  
1.为每一行字符建立一个哈希表，通过哈希表查找  
2.使用STL的set容器，可以查找一个元素是否在set中。

**3.代码**  
C++  
这里实现的是为每一行字符建立哈希表。因为有区分大小写，所以把大小写字母都加进了哈希表。代码有点长。

vector<string> findWords(vector<string>& words) {
            bool** hashTable = new bool*[3];
            for (int i = 0; i < 3; i++)
                hashTable[i] = new bool[256]();
            char one[20] = { 'Q','W','E','R','T','Y','U','I','O','P','q','w','e','r','t','y','u','i','o','p' };
            char two[18] = { 'A','S','D','F','G','H','J','K','L','a','s','d','f','g','h','j','k','l' };
            char three[14] = { 'Z','X','C','V','B','N','M','z','x','c','v','b','n','m' };
            for (int i = 0; i < 20; i++)
                hashTable[0][one[i]] = 1;
            for (int i = 0; i < 18; i++)
                hashTable[1][two[i]] = 1;
            for (int i = 0; i < 14; i++)
                hashTable[2][three[i]] = 1;
            vector<string> result;
            for (int i = 0; i < words.size(); i++) {
                int m = 0;//标记属于哪一行
                for (int k = 0; k < 3; k++)
                    if (hashTable[k][words[i][0]])
                        m = k;
                for (int j = 0; j < words[i].size(); j++) {
                    if (!hashTable[m][words[i][j]])
                        break;//出现不属于该行的字符
                    if (j == words[i].size()-1 && hashTable[m][words[i][j]])
                        result.push_back(words[i]);
                }
            }
            return result;
        }

python  
查看python solution的时候，我再一次被shock到了。我咋就没想到用正则表达式呢。。在此附上牛人的代码，学习学习。

def findWords(self, words):
        return filter(re.compile('(?i)([qwertyuiop]*|[asdfghjkl]*|[zxcvbnm]*)$').match, words)

(\[qwertyuiop\]*|\[asdfghjkl\]*|\[zxcvbnm\]\*) 这段正则是匹配字符的

(?i) 这个是忽略大小写  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/32b6ac0f8ca84748903342f2ae2db1a8.png