Determine which sentences contain the set of phrases I am trying to solve this HackerRank challenge which asks to write a function that prints the indexes of all sentences which contain the query words. For example, if the inputs to the function are:

textQueries(sentences, queries)
textQueries(['jim likes mary','kate likes tom', 'tom does not like jim'],['jim tom', 'likes'])


Then the function will print

2
0 1


If there is no sentence contains the query words, -1 will be printed

The constraints for the inputs are:


The length of the sentences and queries lists will not exceed 10000.
The number of words in any sentence or query is from 1 to 10 words.
Each word has at most 11 characters.
No word appears in more than 10 sentences.
Each word consists of uppercase and lowercase English letters only.


My attempt so far is to create a hashmap which maps each single query word with a set that contains the indexes to the sentences which contain that word, then I intersect those sets with each other to get the final set. My code runs fine, but it is slow for large test cases. Is there any way I can have it optimized?

def textQueries(sentences, queries):
    word_map = {}
    for query in queries:
        query_words = query.split()
        final_set = set([])
        set_modified = False
        for query_word in query_words:
            if query_word in word_map:
                if len(final_set) == 0 and not set_modified:
                    final_set = word_map[query_word]
                    set_modified = True
                    continue
                elif len(final_set) == 0 and set_modified:
                    break
                else:
                    final_set = final_set.intersection(word_map[query_word])
                    continue
            else:
                sentences_contain_word = []
                for index, sentence in enumerate(sentences):
                    words = sentence.split()
                    if query_word in words:
                        sentences_contain_word.append(index)
                        if len(sentences_contain_word) &gt;= 10:
                            break
                word_map[query_word] = set(sentences_contain_word)
                if len(final_set) == 0 and not set_modified:
                    final_set = word_map[query_word]
                    set_modified = True
                elif len(final_set) == 0 and set_modified:
                    break
                else:
                    final_set = final_set.intersection(word_map[query_word])
        if len(final_set) == 0:
            print(-1)
        else:
            for index in sorted(final_set):
                print(str(index), end=' ')
            print()
Your code is fairly readable, but I find it quite dense. Here are some general things you could do to improve it:


Use vertical white space to separate different areas of the code.
Provide a docblock at the top outlining the algorithm you are using.
Use more than one function to break your code into smaller chunks.


With that advice out of the way, let's look at your performance with an eye to the worst possible case:

def textQueries(sentences, queries):
    for query in queries:             # Worst case: 10,000 times
        ...
        for query_word in query_words:  # Worst case: 10 times
            if query_word in word_map:
                    final_set.intersection  # Worst case: O(10,000) in C
            else:
                for ... in enumerate(sentences):  # Worst case: 10,000 times
                if ... else:
                    final_set.intersection  # Worst case: O(10,000) in C


According to me, your code runs worst case in \$O(Q \times W \times S)\$ where \$Q\$ is the number of queries, \$W\$ is the number of words in the query, and \$S\$ is the number of sentences. (The number of words in the sentences is hidden behind a split, but it's in C so we'll let it go by.)

There's no question you need to split the sentences and split the queries into separate words, somehow. But you are nesting your loops when the "best" way to loop is to do them one after the other. If you can convert from this:

for q in Q:
    for s in Q:
        pass


to something like this:

for s in S:
    pass

for q in Q:
    pass


You will have converted from \$O(S \times Q)\$ to \$O(S + Q)\$ which is considerably faster.

Your current approach is to define a set of sentences that contain a particular word. You cache these sets, in case the same words appear again. You intersect the sets for each word in the query, producing a final set of all the sentences that contain all the query words.

This is pretty much guaranteed to fail based on the instructions you quoted:


  No word appears in more than 10 sentences.


In other words, the probability of a "cache hit" is 10/10,000, or 0.1%. Any time you spend maintaining the cache is wasted time.

Suppose you just go through the sentences one time, and build the big dictionary of sets:

sentence_words = collections.defaultdict(set)
for i, s in enumerate(sentences):
    for w in s.split():
        sentence_words[s].add(i)


Then you can go through the query words and do what you were doing before, without any caching:

for q in queries:
    matches = functools.reduce(operator.and_, (sentence_words[w] for w in q.split()))
    matches = [-1] if not matches else sorted(matches)


This will seem very similar to what you were doing, but the difference is that these two loops are run one after the other, providing something like \$O(100,000 + 100,000)\$ performance instead of \$O(100,000 \times 10,000)\$. It's that last operator that makes all the difference.