Leetcode – Keyboard Row Solution in Python

Spread the love

Introduction

In this article, we will deeply analyze one of the string manipulation problems from Leetcode called “Keyboard Row”. We will solve this problem using Python and explore different approaches to solve it.

The Keyboard Row problem is as follows:

Given a List of words, return the words that can be typed using letters of alphabet on only one row of American keyboard.

Example:

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

This is because the words “Alaska” and “Dad” can be typed using only the letters present in the second and the first rows of the American keyboard respectively.

Here are the rows for reference:

  1. QWERTYUIOP
  2. ASDFGHJKL
  3. ZXCVBNM

Approach 1: Naive Approach

One simple way to solve this problem is to create three sets of characters, one for each row on the keyboard. For each word in the input list, we can check if all characters of the word are in any one of the three sets. If this is the case, we can add the word to the output list.

def findWords(words):
    # Creating sets for each row
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    # Output list to store the result
    output = []
    
    # Loop through each word in the input list
    for word in words:
        # Convert the word to lowercase to make the comparison case-insensitive
        w = set(word.lower())
        # Check if the word is in any one row
        if w.issubset(row1) or w.issubset(row2) or w.issubset(row3):
            output.append(word)
    
    return output

While this approach is simple, it’s not the most efficient one as we’re looping through each word and checking if it’s a subset of any of the three sets.

Approach 2: Using List Comprehensions

We can further optimize the naive approach by using list comprehensions in Python. This approach essentially condenses the for loop into a single line.

def findWords(words):
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    return [word for word in words if set(word.lower()).issubset(row1) or set(word.lower()).issubset(row2) or set(word.lower()).issubset(row3)]

This approach is concise but it still has the same complexity as the naive approach.

Approach 3: Using Dictionary for Mapping

We can also use a dictionary to map each character to its respective row number. This allows us to determine the row of the first character of each word and then check if all the characters in the word belong to the same row.

def findWords(words):
    # Mapping each character to the row number
    char_to_row = {char: 1 for char in 'qwertyuiop'}
    char_to_row.update({char: 2 for char in 'asdfghjkl'})
    char_to_row.update({char: 3 for char in 'zxcvbnm'})
    
    output = []
    
    for word in words:
        if len(word) == 0:
            continue
        
        # Determine the row of the first character
        row = char_to_row[word[0].lower()]
        # Check if all characters in the word belong to the same row
        if all(char_to_row[c.lower()] == row for c in word):
            output.append(word)
    
    return output

This approach is slightly more optimized as it doesn’t check for subset conditions explicitly.

Approach 4: Optimizing Memory Usage

The memory footprint can be reduced by avoiding the creation of new sets for each word. Instead, we can iterate over the characters in the word and use a boolean flag to check if they all belong to the same row.

def findWords(words):
    rows = ["qwertyuiop", "asdfghjkl", "zxcvbnm"]
    
    output = []
    
    for word in words:
        if word:
            # Find which row the first character is in
            row = next((r for r in rows if word[0].lower() in r), None)
            # Check if all characters are in the same row
            if row and all(c.lower() in row for c in word):
                output.append(word)
    
    return output

This approach optimizes memory usage as it doesn’t create additional sets for each word.

Conclusion

We have explored four different approaches to solve the Keyboard Row problem on Leetcode using Python. These approaches ranged from the naive approach to more optimized solutions with reduced complexity and memory usage. Depending on the size of the input and constraints, you might choose one approach over another. The trade-offs among readability, memory usage, and performance should be considered according to the requirements of your specific application.

Leave a Reply