Python：从列表中删除其他元素的前缀

Question

获取不包含任何其他元素作为前缀的元素列表的最快（＆python）方法。

（元素可以按任何顺序，为了解释清楚起见，元素在这里保持顺序，因此如果需要，必须显式进行排序）

输入是

['AB', 'ABC', 'ABCDEF', 'ABCDEFG', 'BCD', 'DEF', 'DEFGHI', 'EF', 'GKL', 'JKLM']

消除的元素：

'AB' prefix of 'ABC'
'ABC' prefix of 'ABCDEF'
'ABCDEF' prefix OF 'ABCDEFG'
'DEF' prefix of 'DEFGHI'

预期输出

['ABCDEFG', 'BCD', 'DEFGHI', 'EF', 'GKL', 'JKLM']

编辑：

增加一点复杂性（或清晰度）。列表的平均长度从 500 到 900 不等。

Answer 1

如果列表已排序，则每个元素要么是下一个元素的前缀，要么不是其中任何元素的前缀。因此，你可以写：

ls.sort()
[ls[i] for i in range(len(ls))[:-1] if ls[i] != ls[i+1][:len(ls[i])]] + [ls[-1]]

这将是n log(n)排序加上一次遍历列表 ( n)。

对于您当前的排序列表，它也稍微快一些，因为它是线性的，timeit 给出 2.11 us。

一个稍微快一点的实现（但不是渐进的），并且也更Pythonic，使用zip：

[x for x, y in zip(ls[:-1], ls[1:]) if x != y[:len(x)]] + [ls[-1]]

timeit 给出 1.77 us