500. Keyboard Row
1. Description
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.
2. Example
Example 1:
Input: [“Hello”, “Alaska”, “Dad”, “Peace”]
Output: [“Alaska”, “Dad”]
3. Note
- You may use one character in the keyboard more than once.
- You may assume the input string will only contain letters of alphabet.
4. Solutions
My Accepted Solution
n = i_words.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
public:
// vector<string> findWords(vector<string>& words)
vector<string> findWords(vector<string> &i_words)
{
map<char, int> lettersRow =
{
{'q', 1}, {'w', 1}, {'e', 1}, {'r', 1}, {'t', 1}, {'y', 1}, {'u', 1}, {'i', 1}, {'o', 1}, {'p', 1},
{'a', 2}, {'s', 2}, {'d', 2}, {'f', 2}, {'g', 2}, {'h', 2}, {'j', 2}, {'k', 2}, {'l', 2},
{'z', 3}, {'x', 3}, {'c', 3}, {'v', 3}, {'b', 3}, {'n', 3}, {'m', 3}
};
vector<string> result;
for(int i = 0; i < i_words.size(); i++)
{
int letterRow = lettersRow[tolower(i_words[i].front())];
for(auto letter : i_words[i])
{
if(lettersRow[tolower(letter)] != letterRow)
{
letterRow = 0;
break;
}
}
if(letterRow) result.push_back(i_words[i]);
}
return result;
}
};