LeetCode 500. Keyboard Row

29 Jul 2018

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.

Note:

You may use one character in the keyboard more than once.
You may assume the input string will only contain letters of alphabet.

Example:

input:

[“Hello”, “Alaska”, “Dad”, “Peace”]

output:

[“Alaska”, “Dad”]

Solution:

class Solution {
public:
    int GetLine(char key){
        switch(key)
        {
            case 'q':
            case 'Q':
            case 'w':
            case 'W':
            case 'e':
            case 'E':
            case 'r':
            case 'R':
            case 't':
            case 'T':
            case 'y':
            case 'Y':
            case 'u':
            case 'U':
            case 'i':
            case 'I':
            case 'o':
            case 'O':
            case 'p':
            case 'P':
                return 0;
                break;
            case 'a':
            case 'A':
            case 's':
            case 'S':
            case 'd':
            case 'D':
            case 'f':
            case 'F':
            case 'g':
            case 'G':
            case 'h':
            case 'H':
            case 'j':
            case 'J':
            case 'k':
            case 'K':
            case 'l':
            case 'L':
                return 1;
                break;
            case 'z':
            case 'Z':
            case 'x':
            case 'X':
            case 'c':
            case 'C':
            case 'v':
            case 'V':
            case 'b':
            case 'B':
            case 'n':
            case 'N':
            case 'm':
            case 'M':
                return 2;
                break;
            default:
                throw runtime_error{"no match"};
        }
    }
    
    vector<string> findWords(vector<string>& words) {
        vector<string> result;
        for(const auto &word : words){
            if(word.empty()){
                continue;
            }
            int initialGetLine = GetLine(word.front());
            bool oneLiner = true;
            for(auto i = 1U; i < word.size(); ++i){
                if(GetLine(word[i]) != initialGetLine){
                    oneLiner = false;
                    break;
                }
            }
            if(oneLiner){
                result.push_back(word);
            }
        }
        return result;
    }
    
};

This question is really easy, there are multiple ways to solve it. Feel free to use std::vector, std::set, std::map, std::unordered_map or std::unordered_set to store the lines on keyboard for searching. However, using std containers might not be the fastest in this case, for the allocation of memory might not be continuous. A faster way is to create a simple hash table like this:

(Copied from yzhao12’s answer from https://leetcode.com/problems/keyboard-row/discuss/98043/C++-Solution-using-ASCII. I am not sure why he uses incrementing integers on the right side.)

rank[(int)'Q'] = 1;
rank[(int)'W'] = 2;
rank[(int)'E'] = 3;
rank[(int)'R'] = 4;
rank[(int)'T'] = 5;
rank[(int)'Y'] = 6;
rank[(int)'U'] = 7;
rank[(int)'I'] = 8;
rank[(int)'O'] = 9;
rank[(int)'P'] = 10;
rank[(int)'A'] = 11;
rank[(int)'S'] = 12;
rank[(int)'D'] = 13;
rank[(int)'F'] = 14;
rank[(int)'G'] = 15;
rank[(int)'H'] = 16;
rank[(int)'J'] = 17;
rank[(int)'K'] = 18;
rank[(int)'L'] = 19;
rank[(int)'Z'] = 20;
rank[(int)'X'] = 21;
rank[(int)'C'] = 22;
rank[(int)'V'] = 23;
rank[(int)'B'] = 24;
rank[(int)'N'] = 25;
rank[(int)'M'] = 26;

In this case, this entire hash table might be stored in cache. We still need to use if statements to convert lowercase letters to uppercase. It could be better if we generatre a more complete hash table.

The fastest way, however, is to hard-code the hash table into the program (just like what I did in my solution). Now no if statement is needed, and all the computer needs to do to find out the row of a key is doing arithmetic. This will result in faster searching speed. But of course, the drawback is that it will cause the executable file to be larger. It might be dumb to write the entire switch statement by hand. I have written a small piece of Python code to help me generate them automatically.

def GenerateCXXCode():
    resultFormat = 'switch(key)\n{\n%s\n\tdefault:\n\t\tthrow runtime_error{\"no match\"};\n}\n'
    innerLines = ''
    caseFormat = '\tcase \'%s\':\n'
    lines = ['qwertyuiop', 'asdfghjkl', 'zxcvbnm']
    for ind, line in enumerate(lines):
        for j in range(len(line)):
            innerLines += caseFormat%line[j]
            innerLines += caseFormat%chr(ord(line[j]) - 32)
        innerLines += '\t\treturn %d;\n\t\tbreak;\n'%ind

    print(resultFormat % innerLines)

Review on May, 13 2019

Since python is used, I think it is important to emphasize development efficiency. Therefore, I come up with the code as follows.

class Solution:
    rows = [
        'qwertyuiop',
        'asdfghjkl',
        'zxcvbnm'
    ]
    
    def findRow(self, char):
        for i in range(len(self.rows)):
            if char in self.rows[i]:
                return i
        return None
    
    def isSameRow(self, word):
        word = word.lower()
        if len(word) == 0:
            return False
        fromRows = list(map(self.findRow, word))
        pred = lambda x : x == fromRows[0]
        sameRow = map(pred, fromRows)
        return all(sameRow)
        
        
    
    def findWords(self, words: List[str]) -> List[str]:
        return list(filter(self.isSameRow, words))

Programming it is especially fast and joyous becaues you just need to swipe across the keyboard to construct rows. I have used functional programming styles to make it more concise and faster. The runtime is 32 ms, which is faster than 98.94% of Python3 online submissions for Keyboard Row.

Alan Xiang's Blog