python - 删除以相同子字符串开头的第二个项目

Question

我有一个列表l = ['abcdef', 'abcd', 'ghijklm', 'ghi', 'xyz', 'pqrs']
我想删除以相同子字符串开头的元素(如果存在)(在本例中为 'abcd' 和 'ghi')。
注意:在我的情况下，我知道“重复”元素(如果存在)只能是“abcd”或“ghi”。
要删除它们，我使用了这个:

>>> l.remove('abcd') if ('abcdef' in l and 'abcd' in l) else l
>>> l.remove('ghi') if ('ghijklm' in l and 'ghi' in l) else l
>>> l
>>> ['abcdef', 'ghijklm', 'xyz', 'pqrs']

是否有更高效(或更自动化)的方法来做到这一点？

Answer 1

您可以在线性时间和 O(n*m²) 内存中完成(其中 m 是元素的长度):

prefixes = {}
for word in l:
    for x in range(len(word) - 1):
        prefixes[word[:x]] = True

result = [word for word in l if word not in prefixes]

遍历每个单词并创建一个字典，其中包含每个单词的第一个字符，然后是前两个字符，然后是三个字符，一直到除最后一个字符之外的所有字符。然后再次遍历列表，如果某个单词出现在该词典中，则它是列表中某个其他单词的较短子集