Words Typed in One-Row’s American Keyboard

Given a List of words, find out the words that can be typed using letters of alphabet on only one row’s of American keyboard like the image below.

American keyboard

The straightforward solution is iterative each word and find out which row each letter is at. If all letters from a word are from the same row, then the word is pushed to the result vector. However, the implementation may be different, you can use the data-type unordered_set, array, or hash map/table to record the number of row appearances.

The following C++ solution creates a map string that contains the row number (1 to 3) for each alphabet letters ‘a’ to ‘z’. Then we have a count array for 3 rows i.e. zero means no letters of this row appear in the word and 1 means at least 1 letter of this row appear in the word.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        string map = "23321222122233111121131313"; // 'a' to 'z' which row
        vector<string> result;
        for (auto s: words) {
            int count[3] = {0, 0, 0}; // 1 means has letters of this row
            for (auto c: s) {
                count[map[tolower(c) - 'a'] - '1'] = 1;  // set the row
                if (count[0] + count[1] + count[2] != 1) {
                    break; // if already known as 'NOT a one-row word'
                }                
            }
            if (count[0] + count[1] + count[2] == 1) { // only 1 row
                result.push_back(s);
            }
        }
        return result;
    }
};

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        string map = "23321222122233111121131313"; // 'a' to 'z' which row
        vector<string> result;
        for (auto s: words) {
            int count[3] = {0, 0, 0}; // 1 means has letters of this row
            for (auto c: s) {
                count[map[tolower(c) - 'a'] - '1'] = 1;  // set the row
                if (count[0] + count[1] + count[2] != 1) {
                    break; // if already known as 'NOT a one-row word'
                }                
            }
            if (count[0] + count[1] + count[2] == 1) { // only 1 row
                result.push_back(s);
            }
        }
        return result;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —