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

Question

我在过滤字符串列表时遇到了一些麻烦。我发现了一个类似的问题here但这不是我需要的。

输入列表是:

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)) 

编辑

在对大输入数据进行多次测试后，列出了 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 秒

Sample imput data - 每一行都是列表中的一个字符串

Answer 1

这个算法在我的电脑上用了 0.97 秒完成任务，the input file submitted by the author (154MB) :

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) 复杂度时间和内存。