Keyboard Row

• LeetCode: Keyboard Row
• Problem:

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.

• Note:

1. You may use one character in the keyboard more than once.

2. You may assume the input string will only contain letters of alphabet.

• Example:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

• Analysis:

Use a array as a map to store the row number of an alphabet.

Check wheather every row alphabet is in the same row or not.

• Code-Java:

class Solution {
    public String[] findWords(String[] words) {
        int[] pos = {2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3};
        List<String> list = new ArrayList<String>();
        for (String word : words) {
            int len = word.length();
            if (len == 1) {
                list.add(word);
                continue;
            }
            String lWord = word.toLowerCase();
            int i = 1;
            for (; i < len; i++) {
                if (pos[lWord.charAt(i) - 'a'] != pos[lWord.charAt(i - 1) - 'a']) {
                    break;
                }
            }
            if (i == len) {
                list.add(word);
            }
        }
        int size = list.size();
        String[] result = new String[size];
        for (int i = 0; i < size; i++) {
            result[i] = list.get(i);
        }
        return result;
    }
}

• Code - C++:

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        int pos[] = {2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3};
        vector<string> result;
        for (vector<string>::iterator iter = words.begin(); iter != words.end(); iter++) {
            string word = *iter;
            int len = word.length();
            if (len == 1) {
                result.push_back(word);
                continue;
            }
            int i = 1;
            for (; i < len; i++) {
                if (pos[tolower(word[i]) - 'a'] != pos[tolower(word[i - 1]) - 'a']) {
                    break;
                }
            }
            if (i == len) {
                result.push_back(word);
            }
        }
        return result;
    }
};

• Code - Python:

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """
        pos = [2, 3, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 3, 1, 1, 1, 1, 2, 1, 1, 3, 1, 3, 1, 3]
        result = []
        for word in words:
            wordLen = len(word)
            if wordLen == 1:
                result.append(word)
                continue
            for i in range(1, wordLen):
                if pos[ord(word[i].lower()) - ord('a')] != pos[ord(word[i - 1].lower()) - ord('a')]:
                    break
                if i == wordLen - 1:
                    result.append(word)
        return result

• Time Complexity: O(MN), M is the number of words, N is the max length of a word
• Space Complexity: O(M), M is the number of words