Keyboard Row

Difficulty: Easy | Acceptance: 73.80% | Paid: No Topics: Array, Hash Table, String

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of an 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”.

• Examples

• Constraints

• Approach 1: Hash Set

• Approach 2: Character Mapping

• Approach 3: Regular Expression

Examples

Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]
Explanation:
"Hello" cannot be typed since 'h' and 'e' are not in the same row.
"Alaska" can be typed since all letters are in the second row.
"Dad" can be typed since all letters are in the second row.
"Peace" cannot be typed since 'p' is in the first row and 'e' is in the second row.

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

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

Approach 1: Hash Set

Intuition We can store the characters of each keyboard row in a separate set. A word is valid if all its characters are contained within one of these sets.

Steps

• Initialize three sets containing the characters for the top, home, and bottom rows.
• Iterate through each word in the input list.
• Convert the word to lowercase to handle case insensitivity.
• Check if the word is a subset of the first row, the second row, or the third row.
• If it matches any row, add the original word to the result list.

class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        row1 = set("qwertyuiop")
        row2 = set("asdfghjkl")
        row3 = set("zxcvbnm")
        res = []
        for w in words:
            lower_w = w.lower()
            if all(c in row1 for c in lower_w) or all(c in row2 for c in lower_w) or all(c in row3 for c in lower_w):
                res.append(w)
        return res

Complexity

• Time: O(N * L) where N is the number of words and L is the average length of a word.
• Space: O(1) auxiliary space (excluding the output list), as the sets are of fixed size (26).
• Notes: This approach is intuitive and easy to implement. It requires checking membership in a set for every character.

Approach 2: Character Mapping

Intuition Instead of checking sets, we can map every character in the alphabet to its corresponding row index (0, 1, or 2). Then, for a word to be valid, all its characters must map to the same index.

Steps

• Create a map or array of size 26 to store the row index for each letter.
• Iterate through the words.
• For each word, determine the row index of its first character.
• Check if all subsequent characters have the same row index.
• If they do, add the word to the result.

class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        row_map = {}
        for c in "qwertyuiop": row_map[c] = 1
        for c in "asdfghjkl": row_map[c] = 2
        for c in "zxcvbnm": row_map[c] = 3
        res = []
        for w in words:
            lower_w = w.lower()
            if len(set(row_map[c] for c in lower_w)) == 1:
                res.append(w)
        return res

Complexity

• Time: O(N * L) where N is the number of words and L is the average length of a word.
• Space: O(1) auxiliary space, as the map holds a constant 26 entries.
• Notes: This is often slightly faster than the Hash Set approach because it involves a single lookup per character rather than potentially checking multiple sets.

Approach 3: Regular Expression

Intuition We can define a regular expression that matches strings composed exclusively of characters from one specific row. We can then test each word against this pattern.

Steps

• Construct a regex pattern that matches one or more characters from row 1, row 2, or row 3.
• Iterate through the list of words.
• For each word, check if it matches the pattern (case-insensitive).
• Collect all words that match.

import re
class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        pattern = re.compile(r'(?i)([qwertyuiop]+|[asdfghjkl]+|[zxcvbnm]+)')
        return [w for w in words if pattern.fullmatch(w)]

Complexity

• Time: O(N * L) where N is the number of words and L is the average length of a word.
• Space: O(1) auxiliary space.
• Notes: This approach is very concise and leverages built-in string processing capabilities, though regex compilation can have a small overhead.