Keyboard Row Problem


Description

LeetCode Problem 500.

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

In the American keyboard:

  • the first row consists of the characters “qwertyuiop”,
  • the second row consists of the characters “asdfghjkl”, and
  • the third row consists of the characters “zxcvbnm”.

Example 1:

1
2
Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]

Example 2:

1
2
Input: words = ["omk"]
Output: []

Example 3:

1
2
Input: words = ["adsdf","sfd"]
Output: ["adsdf","sfd"]

Constraints:

  • 1 <= words.length <= 20
  • 1 <= words[i].length <= 100
  • words[i] consists of English letters (both lowercase and uppercase).


Sample C++ Code

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
class Solution {
  public:
    vector<string> findWords(vector<string> &words) {
        vector<unordered_set<char>> dict = {
            {'q', 'Q', 'w', 'W', 'e', 'E', 'r', 'R', 't', 'T', 'y', 'Y', 'u', 'U', 'i', 'I', 'o', 'O', 'p', 'P'},
            {'a', 'A', 's', 'S', 'd', 'D', 'f', 'F', 'g', 'G', 'h', 'H', 'j', 'J', 'k', 'K', 'l', 'L'},
            {'z', 'Z', 'x', 'X', 'c', 'C', 'v', 'V', 'b', 'B', 'n', 'N', 'm', 'M'}};

        vector<string> res;

        for (auto &word : words) {
            vector<bool> d(3, true);

            for (auto &ch : word)
                for (int i = 0; i < 3; ++i)
                    if (d[i] && dict[i].find(ch) == dict[i].end())
                        d[i] = false;

            if (d[0] || d[1] || d[2])
                res.push_back(word);
        }

        return res;
    }
};




Related Posts

Find Duplicate Subtrees Problem

LeetCode 652. Given the rootof a binary tree, return all...

Delete And Earn Problem

LeetCode 740. You are given an integer array nums. You...

Degree Of An Array Problem

LeetCode 697. Given a non-empty array of non-negative integers nums,...

Custom Sort String Problem

LeetCode 791. You are given two strings order and s....

Basic Calculator IV Problem

LeetCode 770. Given an expression such as expression = “e...

Sort Characters By Frequency Problem

LeetCode 451. Given a string s, sort it in decreasing...