python - 什么是最快的算法：在字符串列表中，删除作为另一个字符串的子字符串的所有字符串 [Python（或其他语言）]

Question

有一个字符串列表，例如 ["abc", "ab", "ad", "cde", "cde", "de", "def"] 我希望输出是 ["abc", "广告”、“cde”、“def”]

"ab" 被删除，因为它是 "abc" 的子字符串 "cde" 被删除，因为它是另一个 "cde" 的子字符串 "de" 被删除，因为它是 "def" 的子字符串

最快的算法是什么？

我有一个蛮力方法，即 O(n^2) 如下：

def keep_long_str(str_list):
    str_list.sort(key = lambda x: -len(x))
    cleaned_str_list = []
    for element in str_list:
        element = element.lower()
        keep_element = 1
        for cleaned_element in cleaned_str_list:
            if element in cleaned_element:
                keep_element = 0
                break
            else:
                keep_element = 1
        if keep_element:
            cleaned_str_list.append(element)
    return cleaned_str_list

标签： pythonalgorithm

Answer 1

strings = ["abc", "ab", "ad", "cde", "cde", "de", "def"]
unique_strings = []

for s in strings: 
     if all(s not in uniq for uniq in unique_strings):
         unique_strings.append(s)

运行此代码后，unique_strings等于['abc', 'cde', 'def', 'ad'].

注意：这可能不是最快的方法，但它是一个简单的解决方案。