使集合无前缀

Question

是否有标准或最佳算法来使给定的一组字符串无前缀？也就是说，给定一组字符串，丢弃该组中所有具有（较短）前缀的字符串。

以防万一，我最终会在 Python 2.7.

中实现它

Answer 1

[编辑：丢弃具有（不是是）前缀的字符串]

按长度递增的顺序对字符串进行排序。
将每个字符串插入 trie。如果字符的插入会为当前无子节点（即叶节点）创建一个新的子节点，则丢弃当前字符串——它有一个前缀。

[编辑：固定时间复杂度]

第一步对n个字符串进行排序需要O(n log n)的时间。如果平均字符串长度超过 log(n)，那么这个时间复杂度由第二步决定，这需要时间（和 space）与所有输入字符串的总大小成线性关系。它也很容易实现。

Answer 2

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))

使集合无前缀

Make a set prefix-free

python

algorithm

prefix

information-theory

prefixes