algoadvance

Problem Statement:

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

The American keyboard layout has the following rows:

• Row 1: “qwertyuiop”
• Row 2: “asdfghjkl”
• Row 3: “zxcvbnm”

You need to determine which words can be typed using letters from only one of these rows.

Clarifying Questions:

1. Case Sensitivity: Should the solution handle case insensitivity?
   • Yes, we need to ignore case differences.
2. Input Constraints: Can the input list be empty?
   • Yes, but in that case, the output should be an empty list.
3. Character Set: Will the input contain only English letters?
   • Yes, we assume the input contains only English letters.

Strategy:

1. Data Structures: Use sets to store the characters from each row of the keyboard. Sets will allow for fast membership testing.

2. Normalize Case: Convert each word to lowercase to handle case insensitivity.

3. Check Membership: For each word, check if all characters belong to one of the sets. This can be done using set operations in Python.

4. Result Collection: Collect and return words that meet the criteria.

Code:

def findWords(words):
    # Define sets for each keyboard row
    row1 = set("qwertyuiop")
    row2 = set("asdfghjkl")
    row3 = set("zxcvbnm")
    
    result = []
    
    for word in words:
        # Convert word to lowercase for case insensitivity
        lower_word = word.lower()
        # Convert the word to a set of unique characters
        word_set = set(lower_word)
        
        # Check if the set of characters is a subset of any of the rows
        if word_set <= row1 or word_set <= row2 or word_set <= row3:
            result.append(word)
    
    return result

# Example Usage:
words_list = ["Hello", "Alaska", "Dad", "Peace"]
print(findWords(words_list))  # Output: ['Alaska', 'Dad']

Time Complexity:

• Converting each word to lowercase: O(n) where n is the number of characters in a word.
• Set operations: Checking if a set is a subset is on average O(1) per character due to the fixed size of each row set.
• Overall Complexity: O(k * n) where k is the number of words and n is the average length of each word.

The provided solution is efficient and should handle typical constraints comfortably. Do let me know if you have further questions or need additional use cases!

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?