2024-05-13 03:23:07 发布
网友
我有两个字符串列表:
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)时间复杂度的问题
因为a中的值是唯一的,所以您可以在O(n)中创建一个dict来访问和检查O(1)中的元素
a
迭代b并在O(1)中使用dict检查b的每个元素,然后使用set操作将节省时间,还包括b和a中是否存在相同的多个相同元素
b
set
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)
您可以将列表转换为^{},并使用^{}对其执行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'}
因为
a
中的值是唯一的,所以您可以在O(n)中创建一个dict来访问和检查O(1)中的元素迭代
b
并在O(1)中使用dict检查b的每个元素,然后使用set
操作将节省时间,还包括b
和a
中是否存在相同的多个相同元素您可以将列表转换为^{} ,并使用^{} 对其执行intersection:
集合交集返回两个集合中通用的元素。但是请注意:由于
set
是无序的,如果需要,您将无法维护列表a
或b
中的顺序下面是使用^{} 方法实现相同功能的函数方法:
相关问题 更多 >
编程相关推荐