python - セットをプレフィックスなしにする

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. 各文字列をtriに挿入します。文字の挿入により、現在子のない (つまり、リーフ) ノードの新しい子ノードが作成される場合は、現在の文字列を破棄します。これにはプレフィックスがあります。

[編集: 時間の複雑さを修正]

最初のステップでは、n 個の文字列をソートするのに O(n log n) 時間がかかります。平均文字列長が log(n) を超える場合、この時間の複雑さは、すべての入力文字列の合計サイズに比例して時間 (およびスペース) がかかる 2 番目のステップによって支配されます。実装も非常に簡単です。