Python中两个字符串列表中的公共字符串

Question

我有两个字符串列表：

a = ['ab','ac','ad',..., 'aba','abc',...] # n = 10000 of unique strings
b = ['ab', 'ac', ..., 'ab']               # m = 100 have duplicates
c = []

如何在这两个字符串之间找到公共字符串？我的解决方案以m*n复杂度运行（对吗？）：

    for i in a:
        if i in b:
            c.append(i)

有没有办法解决O（m）时间复杂度的问题

Answer 1

您可以将列表转换为^{}，并使用^{}对其执行intersection：

>>> a = ['ab','ac','ad','aba','abc']
>>> b = ['ab', 'ac', 'ab']

>>> set(a) & set(b)
{'ab', 'ac'}

集合交集返回两个集合中通用的元素。但是请注意：由于set是无序的，如果需要，您将无法维护列表a或b中的顺序

下面是使用^{}方法实现相同功能的函数方法：

>>> set(a).intersection(b)
{'ac', 'ab'}