python - 在列表列表中搜索列表的快速方法

Question

我有一个句子列表和一个查询列表。查询有不同的空格分隔的单词，我必须找到包含所有查询的句子并打印句子的索引。 示例:

3
hey how are you
how do you do
how are you doing
2
how
how are

输出:

0 1 2
0 2

输入结构是这样的:

sentences = ['hey how are you' , 'how do you do' , 'how are you doing']
queries = ['how', 'how are']

我一直在使用 O(n^3) 算法，但它非常慢并且给了我一个 TLE。有没有更快的方法，也许是正则表达式，但我一直无法弄清楚如何构建表达式？

输入大小限制为 10^4。

我的代码:

def textQueries(sentences, queries):
def maptoDict(sentence):
    d = {}
    for word in sentence.split():
        if word not in d.keys():
            d[word] = 1
        else:
            d[word] += 1
    return d
s = list(map(maptoDict,sentences))
q = list(set(query.split()) for query in queries)
for query in q:
    res = []
    for i in range(len(s)):
        if query.issubset(set(s[i].keys())):
            res.append(i)
    if not len(res):
        res.append(-1)
    for r in res:
        print(r, end = ' ')
    print()

Answer 1

Python 支持称为 set 的数据结构.您可以对句子进行后处理，以生成单词到集合的映射。

也就是说，像这样的 map :

word_in_sentences["how"] = set(0, 1, 2)

使用该数据结构，您可以计算所有查询词的集合交集。这将为您提供一个包含查询中所有单词的集合，而不用担心单词的顺序。

一旦您将句子过滤到较小的组，进行任何排序搜索应该会更快。