Keyboard Row - Leetcode Solution

Problem Statement:

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"]

Explanation: Only "Alaska" and "Dad" can be typed using letters of alphabet on only one row's of keyboard.

Example 2:

Input: ["qwee","bdag","jikl","uonm"] Output: ["qwee","jikl"]

Explanation: Only "qwee" and "jikl" can be typed using letters of alphabet on only one row's of keyboard.

Approach:

This problem can easily be solved by defining the keyboard row characters and checking whether the given word contains all its characters from a single row of the keyboard or not.

• We define 3 lists for 3 keyboard rows.
• For every word in the given input list, we convert it into the lowercase to eliminate the case differences.
• Then we check whether all the characters in the word are present in a single row of the keyboard amongst the three defined keyboard rows.
• If all characters belong to the same row, then we consider that word as a valid one for the required output.
• We append all the valid words in the output list and return it.

Pseudo-code:

Let’s code the above approach in python:

def findWords(words: List[str]) -> List[str]:

  row1 = set('qwertyuiop')
  row2 = set('asdfghjkl')
  row3 = set('zxcvbnm')
  
  res = []
  
  for word in words:
      
      w = set(word.lower())
      
      if w.issubset(row1) or w.issubset(row2) or w.issubset(row3):
          res.append(word)
          
  return res

Input:

["Hello","Alaska","Dad","Peace"]

Output:

["Alaska","Dad"]

Time Complexity:

The time complexity of the above solution is O(N*K), where N is the number of words in the given input list and K is the maximum length of a word in the input list. Since we are iterating through every word and every character in the given input list, its time complexity will be linear in the worst case.

Space Complexity:

The space complexity of this solution is O(1), as we have used constant extra space to define the 3 keyword rows and used a single output list to store all the valid words.

Conclusion:

This solution provides an efficient and elegant way to solve the given problem using basic set operations. We have defined the three keyboard rows and checked whether all the characters of the given word belong to the same row of the keyboard or not. Finally, we have filtered out all the valid words in a single output list.

1