Keyboard Row Python Solution with Tests

Tested Python solution for LeetCode 500 with 16 pytest cases. Generate a practice environment with lcpy.

LeetCode 500, Easy. Topics: Array, Hash Table, String. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 16 parametrized pytest cases, and a playground notebook:

lcpy gen -n 500   # by problem number
lcpy gen -s keyboard_row   # by problem name

​

Problem

Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.

Note that the strings are case-insensitive, both lowercased and uppercased of the same letter are treated as if they are at the same row.

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

Input: words = ["Hello","Alaska","Dad","Peace"]
Output: ["Alaska","Dad"]
Explanation: Both "a" and "A" are in the 2nd row of the American keyboard due to case insensitivity.

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(n * m) where n = len(words), m = max word length
    # Space: O(1) (row sets are constant size)
    def find_words(self, words: list[str]) -> list[str]:
        rows = [set("qwertyuiop"), set("asdfghjkl"), set("zxcvbnm")]
        return [word for word in words if any(set(word.lower()) <= row for row in rows)]

​

Complexity

Time	Space
O(n * m) where n = len(words), m = max word length	O(1) (row sets are constant size)

​

Tags