[Daily Leetcode]500. Keyboard Row

Question:

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.

Example 1:

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

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.

Solution:

class Solution(object):
    def findWords(self,words):
        """
        :type words: List[str]
        :rtype: List[str]
        """

        dict = {'q': ['q','w','e','r','t', 'y', 'u', 'i', 'o', 'p'],
                'a': ['a','s','d','f','g','h','j','k','l'],
                'z': ['z','x','c','v','b','n','m']
                }
        output = []
        for i in words:
            x = i.lower()
            if x[0] in dict['q']:
                for k in range(len(i)):
                    if x[k] not in dict['q']:
                        k = k -1
                        break
                if k == len(i) - 1:
                    output.append(i)

            if x[0] in dict['a']:
                for k in range(len(i)):
                    if x[k] not in dict['a']:
                        k = k - 1
                        break
                if k == len(i) - 1:
                    output.append(i)

            if x[0] in dict['z']:
                for k in range(len(i)):
                    if x[k] not in dict['z']:
                        k = k -1
                        break
                if k == len(i) - 1:
                    output.append(i)

        return output

Analysis:

The solution represented above is very straightforward, with the usage of dictionary in python and the trick of extracting single letter from words by treating the string variable as a list. Thought the solution is very forthright, it takes patience to write and debug for beginners. There is only one point to notice: why I should add a ‘k = k -1’ before break? The reason is simple as if we do not add this line to the code, words like ‘sdddw’ whose all but last letters are in the key would be included in the output as ‘k’ accumulates at the beginning of each loop.

Is there any simpler way?

Of course the answer is yes! Let’s analysis the code:

class Solution(object):
    def findWords(self, words):
        """
        :type words: List[str]
        :rtype: List[str]
        """

        _set = set
        row1 = _set('qwertyuiopQWERTYUIOP')
        row2 = _set('asdfghjklASDFGHJKL')
        row3 = _set('zxcvbnmZXCVBNM')
        row_words = []
        for w in words:
            w_set = _set(w)
            if w_set <= row1 or w_set <= row2 or w_set <= row3:
                row_words.append(w)
        return row_words

you would be amazed at how simple this code is. Then how does it work: it uses a trick: set. So what is set? It is a list-like variable but without repeated element, which means set(Apple) = {‘A’, ‘p’, ‘l’, ‘e’}. The only thing we have to do next is judging if the word is in the same set of each Row, a ‘<=' would do this easy task for us  

Leave a Reply

Your email address will not be published. Required fields are marked *