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. 将每个字符串插入到trie中。如果插入一个字符会为当前无子节点（即叶）节点创建一个新的子节点，则丢弃当前字符串——它有一个前缀。

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

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