两个list，如何判断A中的元素是否存在B的元素中

Question

问题：
list_a = [key1,key2,key3...keyn]
list_b = ['1234343key1','weewqsfsdfkey2',........'lkadsadsadsa']

list_a，可以理解为一个关键字集合；
list_b，可以理解为一个长字符串集合，每个元素都比较长，可能包括list_a中元素，也可能不包括。

如何判断list_a中元素是否包含在list_b中。最常用的方法是双层for循环：

    for b in list_b:
        for a in list_a:
            if a in b:
                print(a)

这种方式的时间复杂度为O(m*n)，数据量大就GG。
所以求问比较快速的算法。

Answer 1

似乎大部分回答并没有解决时间复杂度问题，大家在考虑消减循环层次时忽略了字符串匹配本身的复杂度。
假设：

len(key) == 3
len(long_str1) == 10
len(long_str2) == 10

你们说下面哪组更耗时？
1.

key in long_str1
key in long_str2

2.

key in (long_str1 + long_str2)

想必大家心中有答案了，第1组匹配两个字符串要进行 (10-3)*2 轮比较，第2组是(10*2)-3轮，并且long_str1 + long_str2 产生了新的子串，逻辑上是错误的。

楼主的问题到底有没有更低时间复杂度的解决方法，我觉得有，但要牺牲空间。
最坏情况下，list_b中的每个long_str元素，都要做n次 key in long_str 判断，n越大，耗时就越可观；反过来说同样，key要同每个long_str做for key in long_str操作...

预先把所有的long_str的所有子串放入哈希表，就能把一个遍历list_b并逐个字串匹配key的计算，缩减到复杂度为O(1)的哈希查询操作。先做个准备 python求字符串集的所有子串

看完上面链接的问题，你知道把list_b转换成一个哈希也不难（我们用set）

set_a = {s[i:j+1] for s in list_b for i in range(len(s)) for j in range(i, len(s))}
for i in list_a:
    if i in set_a:
        print(i)

因为对于每个long_str，都有其长度的阶乘个子串，所以这个set_a会很大。如果这个问题约束key是定长，那还好些。

Answer 2

list(set(a) & set(b))

Answer 3

可以考虑使用hashset存储关键字集合，时间复杂度可以减少到O(n)。或者如果关键字集合能保证有序的话，可以用二分法。比直接遍历稍微好一点。

只是判断是否包含的话，只要检测到存在一个相同的元素就可以立即返回了，不需要把剩下的元素都过一遍

Answer 4

如果元素判断相同自然可以用set,不过这里不适用.
需要匹配关键词的话简单点先合并字符串(不考虑连续字符串各有一部分组成关键词的情况.)

res = [i for i in list_a if i in ''.join(list_b)]

或使用正则:

import re

res = re.findall('|'.join(list_a), ''.join(list_b))

如果字符串太长或需要语义准确可以先对list_b中的字符串分词, 然后求set的交集或其他处理.
如 ['市长'] 不匹配 ['南京市长江大桥']
以上仅从应用角度考虑.

Answer 5

将python层面的操作转嫁到C编译的内置函数contain（即in关键字）上，代码如下。

>>> list_a = ['key1', 'key2', 'key3']
>>> list_b = ['1234343key1', 'weewqsfsdfkey2', 'lkadsadsadsakey3']
>>> long_str=', '.join(list_b)
>>> long_str
'1234343key1, weewqsfsdfkey2, lkadsadsadsakey3'
>>> for key in list_a:
...     if key in long_str:
...         print(key)
... 
key1
key2
key3

需要注意的是，以上代码在算法上未必高效，但是实际执行效率应该是变高的。

Answer 6

数组元素对比，可以参考 arrayDiffBy

Answer 7

可以将list_b转成set；然后遍历list_a调用set.add；如果是false，说明b中存在a的元素。

Set<String> set = new HashSet(list_b);
for(String str : list_a) {
    if (!set.add(str)) {
      // 说明存在，直接break
      break;
    }
}

Answer 8

可以将list_b = ['1234343key1','weewqsfsdfkey2',........'lkadsadsadsa'] 数字的所有字符串 连起来："1234343key1,weewqsfsdfkey2,...." 然后lista 用n个元素同时从前往后同时遍历listb字符串，按字符匹配