mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
30 lines
1.1 KiB
Markdown
30 lines
1.1 KiB
Markdown
# [500. Keyboard Row](https://leetcode.com/problems/keyboard-row/description/)
|
||
# 思路
|
||
题目意思就是给定一个字符串，若字符串中的每个字母来自键盘上的同一行，则输出。
|
||
我们可以将字母按照键盘布局分类，从上到下分别为0、1、2类。对于每个字符串，遍历一遍，若属于同一类则可输出。
|
||
时间复杂度O(n)
|
||
# C++
|
||
```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;
|
||
}
|
||
};
|
||
```
|