Сделать набор без префикса

Question

Существует ли стандартный или лучший алгоритм, позволяющий сделать данный набор строк без префиксов? То есть, учитывая набор строк, выкинуть все строки, которые имеют (более короткий) префикс также в этом наборе.

В случае, если это имеет значение, я в конечном итоге собираюсь реализовать это в Python 2.7.

Answer 1

strings = ['a', 'apple', 'b', 'beta', 'c', 'd']

def prefices_only(strlist):
    ordered = sorted(strlist)
    last = ordered[0]
    results = [last]

    for c in ordered:
        if not c.startswith(last):
            last = c
            results.append(c)

    return results

print(prefices_only(strings))

Answer 2

[РЕДАКТИРОВАТЬ: отменить строки, которые имеют (не являются) префиксы]

1. Сортировка строк в порядке увеличения длины.
2. Вставьте каждую строку в дерево. Если вставка символа создаст новый дочерний узел для текущего бездетного (т. Е. Конечного) узла, отбросьте текущую строку - у нее есть префикс.

[РЕДАКТИРОВАТЬ: Исправлена ​​сложность времени]

Первый шаг занимает O(n log n) времени для сортировки n строк. Если средняя длина строки превышает log(n), то в этой временной сложности преобладает второй шаг, который занимает линейное время (и пространство) в общем размере всех входных строк. Это тоже довольно легко реализовать.