LeetCode 500: Keyboard Row Solution in Python – A Step-by-Step Guide

What Is LeetCode 500: Keyboard Row?

In LeetCode 500: Keyboard Row, you’re given an array of strings words, and your task is to return a list of all words that can be typed using letters from only one row of a standard QWERTY keyboard, which has three rows: "qwertyuiop" (top), "asdfghjkl" (middle), and "zxcvbnm" (bottom). Case doesn’t matter, so "Dad" and "dad" are the same. For example, with words = ["Hello", "Alaska", "Dad", "Peace"], the result is ["Alaska", "Dad"] because "Alaska" fits the top row and "Dad" fits the middle row, while "Hello" and "Peace" use multiple rows. It’s like testing your typing prowess, sticking to one row per word for a clean, single-handed tap dance.

Problem Statement

• Input: words (List[str])—array of strings.
• Output: List[str]—words typable on one keyboard row.
• Rules:
• QWERTY rows: "qwertyuiop", "asdfghjkl", "zxcvbnm".
• Case-insensitive: treat 'A' and 'a' the same.
• Word must use letters from only one row.

Constraints

• \( 1 \leq words.length \leq 20 \).
• \( 1 \leq words[i].length \leq 100 \).
• words[i] consists of English letters (upper or lowercase).

Examples to Get Us Started

• Input: words = ["Hello","Alaska","Dad","Peace"]
• Output: ["Alaska","Dad"] ("Alaska" → top, "Dad" → middle).
• Input: words = ["omk"]
• Output: [] ("omk" spans middle and bottom rows).
• Input: words = ["adsf","sfd"]
• Output: ["adsf","sfd"] (Both fit middle row).

Understanding the Problem: Typing the Tune

To solve LeetCode 500: Keyboard Row in Python, we need to filter words to keep only those whose letters all belong to one of the three QWERTY rows: "qwertyuiop", "asdfghjkl", or "zxcvbnm", ignoring case. A naive approach—mapping each character to its row and checking—could work but might be inefficient with repeated lookups. The key? Use sets for each row and check if a word’s letter set is a subset of any row set, achieving O(n * k) time (n = words length, k = max word length) with O(1) space for predefined sets. We’ll explore:

• Best Solution (Set-Based Row Checking): O(n * k) time, O(1) space—fast and optimal.
• Alternative Solution (Brute Force Character Mapping): O(n * k) time, O(k) space—simple but less efficient.

Let’s dive into the set-based solution—it’s the typist’s swift keyboard we need.

Best Solution: Set-Based Row Checking

Why This Is the Best Solution

The set-based row checking is the top pick because it’s O(n * k) time (n = words length, k = max word length) and O(1) space (excluding output), efficiently filtering words by converting each word to a set of lowercase letters and checking if it’s a subset of any of the three predefined QWERTY row sets. It leverages Python’s set operations for fast lookups and avoids per-character row mapping, making it both elegant and optimal. It’s like tapping out words with a magic keyboard that lights up only when all letters stay in one row—smart and streamlined!

How It Works

Here’s the strategy:

• Step 1: Define row sets:
• row1 = set("qwertyuiop"), row2 = set("asdfghjkl"), row3 = set("zxcvbnm").
• Step 2: Process each word:
• Convert word to lowercase set of letters.
• Check if subset of row1, row2, or row3.
• If true for any row, add original word to result.
• Step 3: Return result list.
• Why It Works:
• Set subset check ensures all letters are from one row.
• Predefined sets make lookups O(1) per character.

Step-by-Step Example

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

• Init:
• row1 = {'q','w','e','r','t','y','u','i','o','p'}.
• row2 = {'a','s','d','f','g','h','j','k','l'}.
• row3 = {'z','x','c','v','b','n','m'}.
• Result = [].
• "Hello": {'h','e','l','l','o'} → row1 (e,o), row2 (h,l), False.
• "Alaska": {'a','l','a','s','k','a'} → all in row2, True, add "Alaska".
• "Dad": {'d','a','d'} → all in row2, True, add "Dad".
• "Peace": {'p','e','a','c','e'} → row1 (p,e), row2 (a), row3 (c), False.
• Result: ["Alaska", "Dad"].

Example: words = ["adsf","sfd"]

• "adsf": {'a','d','s','f'} → all in row2, True.
• "sfd": {'s','f','d'} → all in row2, True.
• Result: ["adsf", "sfd"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def findWords(self, words: List[str]) -> List[str]:
        # Step 1: Define row sets
        row1 = set('qwertyuiop')
        row2 = set('asdfghjkl')
        row3 = set('zxcvbnm')

        # Step 2: Process each word
        result = []
        for word in words:
            # Convert to lowercase set
            word_set = set(word.lower())
            # Check if subset of any row
            if word_set.issubset(row1) or word_set.issubset(row2) or word_set.issubset(row3):
                result.append(word)

        # Step 3: Return result
        return result

• Line 4-6: Define sets for QWERTY rows.
• Line 9-14: Process words:
• Convert word to lowercase set.
• Check if subset of any row using issubset.
• If true, add original word to result.
• Line 17: Return result.
• Time Complexity: O(n * k)—n words, k chars per word (set ops O(k)).
• Space Complexity: O(1)—fixed row sets, O(k) per word temp set ignored.

It’s like a one-row typist’s charm!

Alternative Solution: Brute Force Character Mapping

Why an Alternative Approach?

The brute force character mapping—O(n * k) time, O(k) space—maps each character to its row (1, 2, or 3) using a dictionary, then checks if all characters in a word belong to the same row. It’s less efficient but intuitive, like manually checking each letter’s keyboard home. Good for clarity or learning!

How It Works

• Step 1: Build char-to-row map:
• Map each letter to row number (1, 2, 3).
• Step 2: Process each word:
• Map first char to row.
• Check all chars match that row.
• Step 3: Add valid words to result.
• Step 4: Return result.

Step-by-Step Example

Example: words = ["Hello","Dad"]

• Map: 'q'=1, 'w'=1, ..., 'a'=2, ..., 'z'=3, etc.
• "Hello": h=2, e=1, l=2, o=1 → multiple rows, False.
• "Dad": d=2, a=2, d=2 → all row 2, True.
• Result: ["Dad"].

Code for Brute Force

Copy codeclass Solution:
    def findWords(self, words: List[str]) -> List[str]:
        # Step 1: Build char-to-row map
        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

        # Step 2-3: Process each word
        result = []
        for word in words:
            word_lower = word.lower()
            if not word_lower:  # Empty word
                continue
            row = row_map[word_lower[0]]
            valid = True
            for c in word_lower:
                if row_map[c] != row:
                    valid = False
                    break
            if valid:
                result.append(word)

        # Step 4: Return result
        return result

• Line 4-11: Map chars to rows (1, 2, 3).
• Line 14-25: Check each word’s row consistency.
• Line 28: Return result.
• Time Complexity: O(n * k)—n words, k chars checked.
• Space Complexity: O(k)—map and temp vars.

It’s a slow key checker!

Comparing the Two Solutions

• Set-Based (Best):
• Pros: O(n * k), O(1) space, fast, elegant.
• Cons: Requires set logic.
• Brute Force (Alternative):
• Pros: O(n * k), intuitive.
• Cons: O(k) space per word, slower lookups.

Set-based wins for efficiency.

Edge Cases and Examples

• Input: [] → [].
• Input: [""] → [].
• Input: ["A"] → ["A"].

Set-based handles all perfectly.

Complexity Recap

• Set-Based: Time O(n * k), Space O(1).
• Brute Force: Time O(n * k), Space O(k).

Set-based is the champ.

Key Takeaways

• Set-Based: Check with subsets.
• Brute Force: Map each char.
• Python Tip: Sets speed—see [Python Basics](/python/basics).

Final Thoughts: Tap That Row

LeetCode 500: Keyboard Row in Python is a typist’s playful challenge. Set-based row checking is your fast keyboard, while brute force is a slow typewriter. Want more string fun? Try LeetCode 125: Valid Palindrome or LeetCode 520: Detect Capital. Ready to type some words? Head to Solve LeetCode 500 on LeetCode and tap it today—your coding skills are row-ready!