給定一個(gè)單詞列表欺抗,只返回可以使用在鍵盤(pán)同一行的字母打印出來(lái)的單詞流酬。鍵盤(pán)如下圖所示。
示例:
輸入: ["Hello", "Alaska", "Dad", "Peace"]
輸出: ["Alaska", "Dad"]
注意:
你可以重復(fù)使用鍵盤(pán)上同一字符。
你可以假設(shè)輸入的字符串將只包含字母贡必。
思路:
遍歷每個(gè)單詞俱恶,逐字母判斷是否在同一行雹嗦,如果不在就退出該單詞匹配
性能分析:
時(shí)間復(fù)雜度O(N * maxBit(word))
空間復(fù)雜度為O(1)
具體代碼:
//打表,記錄字母所在行
// 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 key_value[30] = {2, 3, 3, 2, 1,
2, 2, 2, 1, 2,
2, 2, 3, 3, 1,
1, 1, 1, 2, 1,
1, 3, 1, 3, 1, 3};
//翻譯函數(shù)合是,將字符所在行返回
int trans(char c){
if(c >= 'a' && c <= 'z'){
return key_value[c - 'a'];
}
return key_value[c - 'A'];
}
//需求函數(shù)
vector<string> findWords(vector<string>& words) {
vector<string> res;
//遍歷所有單詞
for(int i = 0; i < words.size(); i++){
//type=單詞首字母所在行號(hào)
int type = trans(words[i][0]);
int j;
//遍歷單詞所有字母了罪,判斷是否均為type
for(j = 1; j < words[i].size(); j++){
if(trans(words[i][j]) != type) break;
}
//判斷是否整個(gè)單詞遍歷完成
if(j == words[i].size()){
res.push_back(words[i]);
}
}
return res;
}