Удалить строковый элемент в списке строк, если первые символы совпадают с другим строковым элементом в списке

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

Как подсказывает Джон Колеман в комментариях , вы можете сначала отсортировать предложения, а затем сравнить последовательные предложения. Если одно предложение является префиксом другого, оно появится прямо перед этими предложениями в отсортированном списке, поэтому нам просто нужно сравнить последовательные предложения. Чтобы сохранить исходный порядок, вы можете использовать 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 будет работать так же хорошо .

Answer 2

Существует небольшая неопределенность в том, как вы сформулировали вопрос о том, как бы вы хотели обработать ['a','ab','ac','add']. Я предполагаю, что вы хотите ['ab','ac','add'].

Ниже также предполагается, что у вас нет пустых строк. Это не очень хорошее предположение.

По сути, мы строим дерево из входных значений и сохраняем только конечные узлы. Это, наверное, самый сложный способ сделать это. Я думаю, что обладает потенциалом быть самым эффективным , но я не уверен , и это не то, что вы просили в любом случае .

from collections import defaultdict
from itertools import groupby
from typing import Collection, Dict, Generator, Iterable, List, Union

# Exploded is a recursive data type representing a culled list of strings as a tree of character-by-character common prefixes. The leaves are the non-common suffixes.
Exploded = Dict[str, Union["Exploded", str]]

def explode(subject:Iterable[str])->Exploded:
    heads_to_tails = defaultdict(list)
    for s in subject:
        if s:
            heads_to_tails[s[0]].append(s[1:])
    return {
        head: prune_or_follow(tails)
        for (head, tails)
        in heads_to_tails.items()
    }

def prune_or_follow(tails: List[str]) -> Union[Exploded, str]:
    if 1 < len(tails):
        return explode(tails)
    else: #we just assume it's not empty.
        return tails[0]

def implode(tree: Exploded, prefix :Iterable[str] = ()) -> Generator[str, None, None]:
    for (head, continued) in tree.items():
        if isinstance(continued, str):
            yield ''.join((*prefix, head, continued))
        else:
            yield from implode(continued, (*prefix, head))

def cull(subject: Iterable[str]) -> Collection[str]:
    return list(implode(explode(subject)))

print(cull(['a','ab','ac','add']))
print(cull([ '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']))
print(cull(['a', 'ab', 'ac', 'b', 'add']))

EDIT:
Я сгладил некоторые звонки, надеюсь, легче читать и рассуждать об этом. Меня беспокоит, что я не могу понять сложность этого процесса во время выполнения. Я думаю это O (нм), где m - длина перекрывающихся префиксов, по сравнению с O (нм log (n)) для сравнения строк ...

EDIT:
Я начал этот другой вопрос в Code Review, надеясь, что кто-нибудь поможет мне разобраться в сложности. Кто-то там указал, что написанный код на самом деле не работает: groupby является мусором из-за любой разумной интерпретации его имени. Я поменял вышеприведенный код, и немного легче читать таким образом.

EDIT:
Хорошо, я импортировал некоторые из отличных предложений для CR. На данный момент я почти уверен, что прав в том, что сложность среды выполнения лучше, чем основанная на сортировке опция.

Answer 3

Это способ, которым вы можете достичь этого: -

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 = []
for i in list1:
    bool = True
    for j in list1:
        if id(i) != id(j) and j.startswith(i): bool = False
    if bool: list2.append(i)
>>> list2
['green apples are worse', ' this is another sentence ', 'a boy ran towards the mill and fell']