LeetCode 500: Keyboard Row

Problem Restatement

We are given an array of strings words.

Return the words that can be typed using letters from only one row of an American keyboard.

The keyboard rows are:

Letter case does not matter. For example, A and a belong to the same row. The word must use letters from only one row. The original word should be returned with its original casing.

Input and Output

Function shape:

def findWords(words: list[str]) -> list[str]:
    ...

Examples

Example 1:

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

Check each word:

Answer:

["Alaska", "Dad"]

Example 2:

words = ["omk"]

The letters are not all from one row.

Answer:

[]

Example 3:

words = ["adsdf", "sfd"]

Both words use only the second row.

Answer:

["adsdf", "sfd"]

First Thought: Check Each Row

For each word, we can check whether all its letters are in one of the three keyboard rows.

Represent each row as a set:

set("qwertyuiop")
set("asdfghjkl")
set("zxcvbnm")

Then convert the word to lowercase and check membership.

Key Insight

A word is valid if the set of its lowercase letters is a subset of one keyboard row.

For example:

word = "Alaska"
letters = set(word.lower())

The set is:

{"a", "l", "s", "k"}

All of these letters are in:

set("asdfghjkl")

So "Alaska" is valid.

For "Hello":

{"h", "e", "l", "o"}

These letters are split across rows, so it is invalid.

Algorithm

Create three sets, one for each keyboard row.

For each word:

1. Convert it to lowercase.
2. Convert its letters to a set.
3. Check whether this set is a subset of any keyboard row.
4. If yes, append the original word to the answer.

Return the answer.

Correctness

The algorithm checks each word after converting it to lowercase, so uppercase and lowercase letters are treated the same.

For a word to be typed using one row, every distinct letter in that word must belong to the same row. Converting the word to a set of letters captures exactly the distinct letters used by the word.

If this letter set is a subset of one keyboard row set, then every letter in the word can be typed from that row, so the word is valid.

If the letter set is not a subset of any row, then the word uses letters from at least two rows, so it cannot be typed using one row.

Therefore, the algorithm returns exactly the valid words.

Complexity

Let:

Implementation

class Solution:
    def findWords(self, words: list[str]) -> list[str]:
        rows = [
            set("qwertyuiop"),
            set("asdfghjkl"),
            set("zxcvbnm"),
        ]

        ans = []

        for word in words:
            letters = set(word.lower())

            if any(letters <= row for row in rows):
                ans.append(word)

        return ans

Code Explanation

The keyboard rows are stored as sets:

rows = [
    set("qwertyuiop"),
    set("asdfghjkl"),
    set("zxcvbnm"),
]

For each word, convert it to lowercase and collect its letters:

letters = set(word.lower())

This checks whether all letters come from one row:

if any(letters <= row for row in rows):

The operator <= means “is subset of” for sets.

If the word is valid, append the original word:

ans.append(word)

Testing

def run_tests():
    s = Solution()

    assert s.findWords(["Hello", "Alaska", "Dad", "Peace"]) == ["Alaska", "Dad"]
    assert s.findWords(["omk"]) == []
    assert s.findWords(["adsdf", "sfd"]) == ["adsdf", "sfd"]
    assert s.findWords(["TYPE", "row"]) == ["TYPE", "row"]
    assert s.findWords(["a", "S", "z"]) == ["a", "S", "z"]

    print("all tests passed")

run_tests()

Test meaning: