过滤字符串列表，忽略其他项的子字符串
我想从一个包含字符串和子字符串的列表中筛选出最长的字符串。也就是说，如果列表中的某个项是另一个项的子字符串，那么只返回更长的那个字符串。
我有了这个函数。有没有更快的方法呢？
def filterSublist(lst):
uniq = lst
for elem in lst:
uniq = [x for x in uniq if (x == elem) or (x not in elem)]
return uniq
lst = ["a", "abc", "b", "d", "xy", "xyz"]
print filterSublist(lst)
> ['abc', 'd', 'xyz']
> Function time: 0.000011
4 个回答
O(n) 解决方案：
import collections
def filterSublist1(words):
longest = collections.defaultdict(str)
for word in words: # O(n)
for i in range(1, len(word)+1): # O(k)
for j in range(len(word) - i + 1): # O(k)
subword = word[j:j+i] # O(1)
if len(longest[subword]) < len(word): # O(1)
longest[subword] = word # O(1)
return list(set(longest.values())) # O(n)
# Total: O(nk²)
解释：
为了理解时间复杂度，我在上面的代码中给出了每一行复杂度的上限。瓶颈出现在循环部分，因为它们是嵌套的，所以整体的时间复杂度会是 O(nk²)，其中 n 是列表中单词的数量，而 k 是单词的平均长度或最长长度（例如，上面的代码中 n = 6 和 k = 3）。不过，如果假设单词不是特别长的字符串，我们可以把 k 限制在一个小值，比如说 k=5，这考虑到了 英语词典中的平均单词长度。因此，因为 k 有一个限制值，所以它不算在时间复杂度里，我们得到的运行时间是 O(n)。当然，k 的大小会增加常数因子，特别是当 k 不小于 n 时。对于英语词典来说，这意味着当 n >> k² = 25 时，你会看到比其他算法更好的结果（见下图）。
这个算法的工作原理是将每个独特的子单词映射到包含该子单词的最长字符串上。所以比如说，'xyz' 会查找 longest['x']、longest['y']、longest['z']、longest['xy']、longest['yz'] 和 longest['xyz']，并将它们都设置为 'xyz'。当对列表中的每个单词都这样处理后，longest.keys() 将会是所有单词的独特子单词的集合，而 longest.values() 将只包含那些不是其他单词子单词的单词。最后，longest.values() 可能会有重复的单词，所以通过用 set 包裹起来来去除重复。
可视化时间复杂度
下面我测试了上面的算法（以及你原来的算法），以展示这个解决方案在使用英语单词时确实是 O(n)。我使用 timeit 在一个 包含多达69000个英语单词的列表上进行了测试。我把这个算法称为 filterSublist1，而你的原始算法称为 filterSublist2。
图表显示在对数-对数坐标轴上，这意味着该算法在这个输入集上的时间复杂度由线的斜率给出。对于 filterSublist1，斜率大约是1，意味着它是 O(n1)；而对于 filterSublist2，斜率大约是2，意味着它是 O(n2)。
注意：我没有记录 filterSublist2() 在69000个单词时的时间，因为我不想等太久。
你可以把你的问题用矩阵的形式来表示，如下所示：
import numpy as np
lst = np.array(["a", "abc", "b", "d", "xy", "xyz"], object)
out = np.zeros((len(lst), len(lst)), dtype=int)
for i in range(len(lst)):
for j in range(len(lst)):
out[i,j] = lst[i] in lst[j]
从这里你可以得到 out 的结果：
array([[1, 1, 0, 0, 0, 0],
[0, 1, 0, 0, 0, 0],
[0, 1, 1, 0, 0, 0],
[0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 1],
[0, 0, 0, 0, 0, 1]])
然后，答案就是 lst 中那些列的索引，前提是这些列的 out 的和等于 1（也就是说，字符串只出现在它自己里面）：
lst[out.sum(axis=1)==1]
#array(['abc', 'd', 'xyz'], dtype=object)
补充说明： 你可以用更高效的方法来实现：
from numpy.lib.stride_tricks import as_strided
from string import find
size = len(lst)
a = np.char.array(lst)
a2 = np.char.array(as_strided(a, shape=(size, size),
strides=(a.strides[0], 0)))
out = find(a2, a)
out[out==0] = 1
out[out==-1] = 0
print a[out.sum(axis=0)==1]
# chararray(['abc', 'd', 'xyz'], dtype='|S3')
a[out.sum(axis=0)==1]
顺序重要吗？如果不重要，
a = ["a", "abc", "b", "d", "xy", "xyz"]
a.sort(key=len, reverse=True)
n = len(a)
for i in range(n - 1):
if a[i]:
for j in range(i + 1, n):
if a[j] in a[i]:
a[j] = ''
print filter(len, a) # ['abc', 'xyz', 'd']
虽然效率不高，但很简单。
一个简单的二次时间复杂度的解决方案是这样的：
res = []
n = len(lst)
for i in xrange(n):
if not any(i != j and lst[i] in lst[j] for j in xrange(n)):
res.append(lst[i])
但我们可以做得更好：
假设有一个字符 $，它在你的字符串中没有出现，并且它的值比你所有实际字符的值都要小。
接下来，把所有的字符串用 $ 连接起来，形成一个新的字符串 S。在你的例子中，S = a$abc$b$d$xy$xyz。
你可以用线性时间来构建 后缀数组，也可以使用一个更简单的 O(n log^2 n) 的构建算法，这个我在 另一个回答中提到过。
现在，对于 lst 中的每个字符串，检查它在后缀数组中是否只出现一次。你可以通过两次二分查找来找到这个子字符串的位置，它们在后缀数组中形成一个连续的范围。如果这个字符串出现超过一次，就把它去掉。
如果预先计算了 LCP 信息，这个过程也可以在线性时间内完成。
下面是一个 O(n log^2 n) 的实现示例，改编自 我的后缀数组回答：
def findFirst(lo, hi, pred):
""" Find the first i in range(lo, hi) with pred(i) == True.
Requires pred to be a monotone. If there is no such i, return hi. """
while lo < hi:
mid = (lo + hi) // 2
if pred(mid): hi = mid;
else: lo = mid + 1
return lo
# uses the algorithm described in https://stackoverflow.com/a/21342145/916657
class SuffixArray(object):
def __init__(self, s):
""" build the suffix array of s in O(n log^2 n) where n = len(s). """
n = len(s)
log2 = 0
while (1<<log2) < n:
log2 += 1
rank = [[0]*n for _ in xrange(log2)]
for i in xrange(n):
rank[0][i] = s[i]
L = [0]*n
for step in xrange(1, log2):
length = 1 << step
for i in xrange(n):
L[i] = (rank[step - 1][i],
rank[step - 1][i + length // 2] if i + length // 2 < n else -1,
i)
L.sort()
for i in xrange(n):
rank[step][L[i][2]] = \
rank[step][L[i - 1][2]] if i > 0 and L[i][:2] == L[i-1][:2] else i
self.log2 = log2
self.rank = rank
self.sa = [l[2] for l in L]
self.s = s
self.rev = [0]*n
for i, j in enumerate(self.sa):
self.rev[j] = i
def lcp(self, x, y):
""" compute the longest common prefix of s[x:] and s[y:] in O(log n). """
n = len(self.s)
if x == y:
return n - x
ret = 0
for k in xrange(self.log2 - 1, -1, -1):
if x >= n or y >= n:
break
if self.rank[k][x] == self.rank[k][y]:
x += 1<<k
y += 1<<k
ret += 1<<k
return ret
def compareSubstrings(self, x, lx, y, ly):
""" compare substrings s[x:x+lx] and s[y:y+yl] in O(log n). """
l = min((self.lcp(x, y), lx, ly))
if l == lx == ly: return 0
if l == lx: return -1
if l == ly: return 1
return cmp(self.s[x + l], self.s[y + l])
def count(self, x, l):
""" count occurences of substring s[x:x+l] in O(log n). """
n = len(self.s)
cs = self.compareSubstrings
lo = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) >= 0)
hi = findFirst(0, n, lambda i: cs(self.sa[i], min(l, n - self.sa[i]), x, l) > 0)
return hi - lo
def debug(self):
""" print the suffix array for debugging purposes. """
for i, j in enumerate(self.sa):
print str(i).ljust(4), self.s[j:], self.lcp(self.sa[i], self.sa[i-1]) if i >0 else "n/a"
def filterSublist(lst):
splitter = "\x00"
s = splitter.join(lst) + splitter
sa = SuffixArray(s)
res = []
offset = 0
for x in lst:
if sa.count(offset, len(x)) == 1:
res.append(x)
offset += len(x) + 1
return res
不过，由于解释的开销，这种方法可能会比 O(n^2) 的方法慢，除非 S 真的是非常大（大约 10^5 个字符或更多）。