LeetCode 500. Keyboard Row

Description

https://leetcode.com/problems/keyboard-row/

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:

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

Example 2:

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

Example 3:

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). 

Explanation

Check if characters in words are in the same keyboard row.

Python Solution

class Solution:
    def findWords(self, words: List[str]) -> List[str]:
        results = []
        
        row1 = ["q", "w", "e", "r", "t", "y", "u", "i", "o", "p"]
        row2 = ["a", "s", "d", "f", "g", "h", "j", "k", "l"]
        row3 = ["z", "x", "c", "v", "b", "n", "m"]            
        
        for word in words:
            is_same = True
            prev_row = 0
            
            for c in word.lower():
                row = None
                               
                if c in row1:
                    row = 1
                elif c in row2:
                    row = 2
                elif c in row3:
                    row = 3
            
                if prev_row != 0 and row != prev_row:
                    is_same = False
                    break
                
                prev_row = row
            
            if is_same:
                results.append(word)
                
                
        return results
        
  • Time Complexity: O(N).
  • Space Complexity: O(N).

Leave a Reply

Your email address will not be published.