Python脚本开发：移除字符串列表中的子集元素

Hey there! Let's work through this problem together. First, let's take a look at your current code and fix the logic gaps, then talk about whether that double loop is the best approach.

First off, your existing code has a couple of key issues:

• It adds elements to elements_to_keep multiple times (every time an element isn't a substring of another), leading to duplicate entries.
• More importantly, it doesn't correctly identify subset elements. For example, the 'sentence' string would get added when comparing against 'who is alice'—but we need to discard 'sentence' entirely because it's a subset of 'this is a sentence'.

The Correct Core Logic #

What we actually need to do is: keep a string only if there is no other string in the list that contains it (i.e., it's not a subset of any other element). Strings that are neither subsets nor supersets of any other element (like 'who is alice') should also be kept.

A Fixed (But Still O(n²)) Version #

Let's start with a straightforward, logically correct implementation. This uses a single loop with an any() check to verify if the current string is a subset of any other string:

def keep_supersets(strings):
    result = []
    for s in strings:
        # Check if s is a subset of any other string in the list
        is_subset = any(t != s and s in t for t in strings)
        if not is_subset:
            result.append(s)
    return result

# Test with your example
A = ['this is a sentence', 'who is alice', 'sentence', 'hi i am carrot', 'i am carrot']
print(keep_supersets(A))
# Output: ['this is a sentence', 'who is alice', 'hi i am carrot']

This works correctly, but it's still O(n²) time complexity since we check every string against every other string. For small lists, this is totally fine—but if you're working with large datasets, we can optimize this.

Optimized Approach (Reduce Unnecessary Comparisons) #

Here's a smarter way: since a longer string can never be a subset of a shorter one (assuming we're talking about substring subsets like your example), we can sort the list by string length in descending order first. Then, we only need to check if the current string is already contained in any of the strings we've already kept (which are all longer or equal in length).

def keep_supersets_optimized(strings):
    # Sort strings from longest to shortest
    sorted_strings = sorted(strings, key=lambda x: -len(x))
    result = []
    for s in sorted_strings:
        # Only keep s if it's not a subset of any already kept string
        if not any(s in t for t in result):
            result.append(s)
    # Optional: Restore the original order of kept elements
    return [s for s in strings if s in result]

# Test with your example
print(keep_supersets_optimized(A))
# Output: ['this is a sentence', 'who is alice', 'hi i am carrot']

This cuts down on unnecessary comparisons because we avoid checking shorter strings against each other (since they can't contain one another). The time complexity is still O(n²) in the worst case (if no strings are subsets of each other), but in practice, it's much faster for most real-world cases where there are overlapping subsets.

So, Is the Double Loop Optimal? #

Your original double loop isn't optimal for two reasons: it has logical errors, and even when fixed, a naive double loop doesn't leverage the length-based optimization we just talked about. The optimized version above is better because it reduces the number of comparisons we need to make.

内容的提问来源于stack exchange，提问作者iam.Carrot