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

因为a中的值是唯一的，所以您可以在O（n）中创建一个dict来访问和检查O（1）中的元素

迭代b并在O（1）中使用dict检查b的每个元素，然后使用set操作将节省时间，还包括b和a中是否存在相同的多个相同元素

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


a_dic = {i:1 for i in a}
sol = []

for i in b:
    if a_dic.get(i, None):
        sol.append(i)

Answer 2

您可以将列表转换为^{}，并使用^{}对其执行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'}