获取包含字符串元素的列表，不包括初始列表中以任何其他元素为前缀的元素

我在过滤字符串列表时遇到一些问题。我发现了一个类似的问题here https://stackoverflow.com/questions/22221878/python-delete-substrings-from-list-of-strings但这不是我需要的。

输入列表为：

l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']

预期结果是

['ab', 'xc', 'sdfdg']

结果中项目的顺序并不重要

由于列表的大小很大，过滤功能必须很快

我目前的解决方案是

l = ['ab', 'xc', 'abb', 'abed', 'sdfdg', 'abfdsdg', 'xccc']
for i in range(0, len(l) - 1):
    for j in range(i + 1, len(l)):
        if l[j].startswith(l[i]):
            l[j] = l[i]
        else:
            if l[i].startswith(l[j]):
                l[i] = l[j]

print list(set(l)) 

EDIT

经过对大输入数据的多次测试，列出 1500000 个字符串，我对此的最佳解决方案是：

def filter(l):
    if l==[]:
        return []
    l2=[]
    l2.append(l[0])
    llen = len(l)
    k=0
    itter = 0
    while k<llen:
        addkelem = ''
        j=0
        l2len = len(l2)
        while j<l2len:
            if (l2[j].startswith(l[k]) and l[k]!= l2[j]):
                l2[j]=l[k]
                l.remove(l[k])
                llen-=1
                j-=1
                addkelem = ''
                continue
            if (l[k].startswith(l2[j])):
                addkelem = ''
                break
            elif(l[k] not in l2):
                addkelem = l[k]
            j+=1
        if addkelem != '':
            l2.append(addkelem)
            addkelem = ''
        k+=1
    return l2

执行时间约为 213 秒

输入数据示例 http://soft2u.ro/out.7z- 每一行都是列表中的一个字符串

这个算法在我的电脑上只用了 0.97 秒就完成了任务，作者提交的输入文件 (154MB) http://soft2u.ro/out.txt:

l.sort()

last_str = l[0]
filtered = [last_str]
app      = filtered.append

for str in l:
    if not str.startswith(last_str):
        last_str = str
        app(str)

# Commented because of the massive amount of data to print.
# print filtered

该算法很简单：首先按字典顺序对列表进行排序，然后搜索第一个不以列表中第一个字符串为前缀的字符串，然后搜索下一个不以最后一个无前缀字符串为前缀的字符串，依此类推。

如果列表已经排序（您的示例文件似乎已经排序），您可以删除l.sort()行，这将导致时间和内存的复杂度为 O(n)。