Какой алгоритм самый быстрый: в списке строк удалите все строки, которые являются подстрока другой строки [Python (или другой язык)]

Question

Есть список строк, например ["ab c", "ab", "ad", "cde", "cde", "de", "def"]. Я бы хотел, чтобы вывод был ["ab c", "ad", "cde", "def"]

"ab" было удалено, поскольку это подстрока "ab c", "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

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'].

Примечание. Вероятно, это не самый быстрый способ сделать это, но это простое решение.

Answer 2

Я посмотрел на ответ Джека Муди и Криса Чарли, и мне все еще не нравилось использование all, когда any может вырваться из l oop при первом появлении суперструны, поэтому придумал это изменение:

strings = ["abc", "ab", "ad", "cde", "cde", "de", "def"]
unique_strings = []
for s in sorted(strings, reverse=True):  # Largest first 
    if not any(s in uniq for uniq in unique_strings):
        unique_strings.append(s)
print(unique_strings)  # ['def', 'cde', 'ad', 'abc']

Я не думал, что есть необходимость явной сортировки по строке len, так как она все равно является частью сравнения строк. Приветствия: -)