Leetcode 500题中Python set.issubset()与元素查找的性能对比

Great question! Let’s dive into how your custom solution stacks up against the set.issubset() approach, including why you might see clear performance differences between the two.

First, let’s recap both approaches to set context:

Your Custom Solution #

Here’s your code for reference:

def checkWord(self, word):
    r1 = 'qwertyuiop'
    r2 = 'asdfghjkl'
    r3 = 'zxcvbnm'
    row = 0
    for idx, ch in enumerate(word):
        if idx == 0:
            row = 1 if ch in r1 else 2 if ch in r2 else 3
            continue
        coming_row = 1 if ch in r1 else 2 if ch in r2 else 3
        if row != coming_row:
            return False
    return True

Your logic iterates through each character in the word, checks which keyboard row it belongs to using string membership checks, and verifies all characters stay in the same row as the first one.

set.issubset() Approach #

A typical optimized implementation using sets looks like this:

def checkWord(self, word):
    row1 = set('qwertyuiop')
    row2 = set('asdfghjkl')
    row3 = set('zxcvbnm')
    word_set = set(word.lower())
    return word_set.issubset(row1) or word_set.issubset(row2) or word_set.issubset(row3)

This converts the word and keyboard rows into sets, then checks if all characters in the word are contained within one of the pre-defined row sets.

Performance Differences & Core Reasons #

1. Time Complexity #

• Your solution: For each character in the word, you perform up to 3 string membership checks (ch in r1, ch in r2, etc.). String membership in Python is a linear search (O(m) where m is the length of the string—e.g., 10 characters for row 1). For a word of length k, this results in O(k*m) time per word. In the worst case, each character requires checking all three rows (10+9+7 = 26 operations per character).

• Set approach: Converting the word to a set takes O(k) time. The issubset() method checks if every element in word_set exists in a row set—since set membership is an average O(1) operation (powered by hash tables), this step takes O(min(k, row_size)) time (row sizes are fixed at 10, 9, 7). Overall, this is O(k) time per word, which is drastically faster for longer words.

2. Native Code Overhead #

Another critical factor is that set.issubset() is implemented in optimized C (for CPython), whereas your loop and conditional checks run in pure Python. Native C operations avoid the overhead of Python’s loop iteration, conditional branching, and repeated function calls, making them much faster for repetitive tasks.

3. Space Complexity #

• Your solution: Uses constant extra space (O(1))—only a few variables to track the current row. No additional data structures are created.
• Set approach: Requires O(k) space for the word_set (plus fixed space for the three row sets). For most LeetCode test cases, this is negligible, but it’s worth noting if memory is a strict constraint.

Real-World Impact #

For short words (e.g., 2-3 characters), the performance gap might be barely noticeable. But as word length increases, the set approach pulls ahead dramatically. For example, a 10-character word would require your solution to perform up to 260 operations, while the set approach would do ~10 operations to build the set plus ~10 checks for issubset()—a massive difference in efficiency.

Additionally, your solution has to re-check the row for every character after the first, whereas the set approach only needs to validate the entire word against three fixed sets once.

内容的提问来源于stack exchange，提问作者sharonlyu