500. Keyboard Row
Model: qwen2.5-coder:14b
Topics: Hash Table
FAANG asked: 0
Acceptance rate: 65.9%
Problem Breakdown
The problem asks us to filter an array of words such that only those words which can be typed using letters from a single row of the American keyboard are returned. The keyboard has three rows: "qwertyuiop", "asdfghjkl", and "zxcvbnm". The input is an array of strings, and the output should also be an array of strings that meet the criteria.
Inputs:
- An array of words (
words), where each word consists of English letters (both lowercase and uppercase).
Outputs:
- An array of words that can be typed using letters from only one row of the keyboard.
Implicit Constraints or Edge Cases:
- The input array can be empty.
- Words can contain both uppercase and lowercase letters, but they should be treated as case-insensitive when checking which row they belong to.
- The length of the input array is at most 20, and each word’s length is at most 100.
Intuition
A brute-force approach would involve checking each character of every word against all three rows of the keyboard. This method would be inefficient in terms of time complexity because it would require multiple checks for each character in each word.
The key insight to improve this approach is to pre-process the keyboard rows into a hash table where each letter maps to its corresponding row index (0, 1, or 2). Then, for each word, we can determine if all its characters belong to the same row by checking their mapped indices. This reduces the number of comparisons needed and improves efficiency.
Approach
-
Pre-process Keyboard Rows:
- Create a hash table (
keyboard_map) where each letter (both lowercase and uppercase) maps to its corresponding row index.
- Create a hash table (
-
Filter Words:
- For each word in the input array, convert it to lowercase to handle case insensitivity.
- Check if all characters of the word belong to the same row by comparing their mapped indices.
- If they do, add the word to the result list.
-
Return Result:
- Return the list of words that can be typed using letters from only one row of the keyboard.
Complexity Analysis
- Time Complexity: O(n * m), where
nis the number of words andmis the average length of a word. This is because we need to check each character of each word. - Space Complexity: O(1) for the hash table, as its size is constant (26 letters). The space used by the result list does not count towards this complexity.
Solution
def findWords(words):
# Pre-process keyboard rows into a hash table
keyboard_map = {
'q': 0, 'w': 0, 'e': 0, 'r': 0, 't': 0, 'y': 0, 'u': 0, 'i': 0, 'o': 0, 'p': 0,
'a': 1, 's': 1, 'd': 1, 'f': 1, 'g': 1, 'h': 1, 'j': 1, 'k': 1, 'l': 1,
'z': 2, 'x': 2, 'c': 2, 'v': 2, 'b': 2, 'n': 2, 'm': 2
}
# Function to check if a word can be typed using one row
def is_one_row(word):
row_index = keyboard_map[word[0].lower()]
for char in word:
if keyboard_map[char.lower()] != row_index:
return False
return True
# Filter words that can be typed using one row
result = [word for word in words if is_one_row(word)]
return result
# Example usage
print(findWords(["Hello", "Alaska", "Dad", "Peace"])) # Output: ["Alaska", "Dad"]
print(findWords(["omk"])) # Output: []
print(findWords(["adsdf", "sfd"])) # Output: ["adsdf", "sfd"]
Edge Cases Handled
- Empty Input: If the input array is empty, the function will return an empty list.
- Case Insensitivity: The function treats uppercase and lowercase letters as equivalent by converting them to lowercase before checking their row indices.