500. Keyboard Row

2020, Nov 27 2 mins read

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

Queue

n = i_words.size()
Time complexity: O(n)
Space complexity: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
    }
};

Search

Tags