使设置的前缀无

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），则此时间复杂度由第二步主导，该步骤在所有输入字符串的总大小中采用时间（和空间）线性。 这也很容易实现。