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.
Subscribe to see which companies asked this question.
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include <algorithm>
using namespace std;
class Solution {
public:
void findWords(vector<string>& words) {
vector<string> strs ={ "QWERTYUIOP", "ASDFGHJKL", "ZXCVBNM" };
map<char, int> map;
for (int i = 0; i<strs.size(); i++){
for (char c : strs[i]){
map.insert(pair<char, int>(c, i));//put <char, rowIndex> pair into the map
}
}
vector<string> res;
vector<string> dst(words.size());
for (int i = 0; i < words.size(); i++)
transform(words[i].begin(), words[i].end(), back_inserter(dst[i]), ::toupper);
for (int i = 0; i<dst.size(); i++){
if (dst[i] == "")
continue;
int index = map[dst[i][0]];
for (int j = 0;j<dst[i].size();j++){
if (map[dst[i][j]] != index){
index = -1; //don't need a boolean flag.
break;
}
}
if (index != -1) res.push_back(words[i]);//if index != -1, this is a valid string
}
for (auto w : res){
cout << w << " ";
cout << endl;
}
}
};
int main()
{
vector<string> word = { "Hello", "Alaska", "Dad", "Peace" };
Solution s;
s.findWords(word);
system("pause");
return 0;
}