python - 如果第一个字符与列表中的另一个字符串元素匹配，则删除字符串列表中的字符串元素

Question

我想有效地查找和比较列表中的字符串元素，然后删除那些属于列表中其他字符串元素的部分(具有相同的起点)

list1 = [ 'a boy ran' , 'green apples are worse' , 'a boy ran towards the mill' ,  ' this is another sentence ' , 'a boy ran towards the mill and fell',.....]

我打算得到一个如下所示的列表:

list2 = [  'green apples are worse' , ' this is another sentence ' , 'a boy ran towards the mill and fell',.....]

换句话说，我想从那些以相同首字符开头的元素中保留最长的字符串元素。

Answer 1

根据 John Coleman in comments 的建议，可以先对句子排序，再比较连续的句子。如果一个句子是另一个句子的前缀，它会出现在排序列表中该句子之前，所以我们只需要比较连续的句子。要保留原始顺序，您可以使用 set 快速查找过滤后的元素。

list1 = ['a boy ran', 'green apples are worse', 
         'a boy ran towards the mill', ' this is another sentence ',
         'a boy ran towards the mill and fell']                                                                

srtd = sorted(list1)
filtered = set(list1)
for a, b in zip(srtd, srtd[1:]):
    if b.startswith(a):
        filtered.remove(a)

list2 = [x for x in list1 if x in filtered]                                     

之后，list2如下:

['green apples are worse',
 ' this is another sentence ',
 'a boy ran towards the mill and fell']

使用 O(nlogn) 这比比较 O(n²) 中的所有句子对要快得多，但如果列表不是太长，Vicrobot 的更简单的解决方案将同样有效。