Welcome to Code Review!
So, I am assuming that queries is a list of words we are searching for, and any of them being found is a success. I am also assuming that sentences is a list of strings, with each element subdivide-able into a list of words.
Bugs:
I noticed that your existing code won't see "This is a test." as having the word "test" in it, because of the period. You may need to separate out commas, periods, parentheses and so on for it to work properly, but perhaps this is by design. I am unsure.
Add a Break:
The first thing I see that could be improved is you don't need a flag. Instead of setting exists = False and then keep looping, just add your results if it is there, and then just break. You don't need to search the entire sentence if you have already found it, and you don't need a flag if you are doing the one operation within the loop.
So:
for word in words.split(' '):
if word in s:
results += ' %d' % j if results else '%d' % j
break
This will save you a few iterations for long sentences if the beginning matches.
Tries:
Now, if you want to completely rewrite the whole thing for O(n) passes, (which is the best you can possibly get for text searching), then you can use a "Trie" data structure. The way this works is by inserting all of your text, one character at a time per word, into a variation of a tree. This is O(n) insertion, where n is the number of characters in your input data. Then, for every search term, you go through and find, letter by letter, which words match. This is O(n) where n is the number of characters in each search term, so theoretically much less of an impact than the previous one.
I modified the code that was posted here (under public domain): https://towardsdatascience.com/implementing-a-trie-data-structure-in-python-in-less-than-100-lines-of-code-a877ea23c1a1
Most of it is not my own, but I modified it to fit your function.
class Node(object):
def __init__(self, character):
self.character = character
self.children = []
# A flag to say whether or not we are at the end of our current word.
self.finished = False
# How many times this character appeared in the addition process
self.count = 1
class Trie(object):
def __init__(self):
# Create a root node with a non-character attribute so it won't be confused
# with any of the entries.
self.root = Node(None)
def add(self, word):
# Set our current node to the start/root.
current_node = self.root
for char in word:
in_child = False
# Search for the character in the children of the present node
for child in current_node.children:
if child.character == char:
# We found it, increase the counter by 1 to keep track that another
# word has it as well
child.count += 1
# And point the node to the child that contains this char
current_node = child
in_child = True
break
# We did not find it so add a new chlid
if not in_child:
new_node = Node(char)
current_node.children.append(new_node)
# And then point node to the new child
current_node = new_node
# Everything finished. Mark it as the end of a word.
current_node.word_finished = True
def find_term(self, term):
"""
Check and return
1. If the prefix exsists in any of the words we added so far
2. If yes then how may words actually have the prefix
"""
node = self.root
# If the root node has no children, then return False.
# Because it means we are trying to search in an empty trie
if not self.root.children:
return False, 0
for char in term:
char_not_found = True
# Search through all the children of the present `node`
for child in node.children:
if child.character == char:
# We found the char existing in the child.
char_not_found = False
# Assign node as the child containing the char and break
node = child
break
# Return False anyway when we did not find a char.
if char_not_found:
return False, 0
# Well, we are here means we have found the prefix. Return true to indicate that
# And also the counter of the last node. This indicates how many words have this
# prefix
return True, node.count
def textQueries(sentences, queries):
trie = Trie()
sentences_list = [s.split(' ') for s in sentences]
for sentence in sentences_list:
for word in sentence:
trie.add(word)
for words in queries:
words_list = words.split(' ')
results_list = []
for word in words_list:
results = trie.find_term(word)
if results[0]:
results_list.append(results[1])
if results_list:
print results_list
else: print -1
This will return:
Venkee Enterprises:>python test.py
[2]
[1]
for my input data of:
sentences = ["Hello world, this is a sentence.", "This is also a sentence.", "This, however, is an incomplete"]
queries = ["sentence", "Hello"]
As it was able to find 2 words that match for the query "sentence" and 1 word that matched "Hello".
Hope this helps.
