Write a function called
answer(document, searchTerms)
which returns the shortest snippet of the document, containing all of the given search terms. The search terms can appear in any order.Inputs: (string) document = "many google employees can program" (string list) searchTerms = ["google", "program"] Output: (string) "google employees can program" Inputs: (string) document = "a b c d a" (string list) searchTerms = ["a", "c", "d"] Output: (string) "c d a"
My program below is giving the correct answer but the time complexity is very high since I am doing the Cartesian product. If the input is very high then I am not able to clear to those test cases. I am not able to reduce the complexity of this program, and any help will be greatly appreciated.
import itertools
import sys
def answer(document, searchTerms):
min = sys.maxint
matchedString = ""
stringList = document.split(" ")
d = dict()
for j in range(len(searchTerms)):
for i in range(len(stringList)):
if searchTerms[j] == stringList[i]:
d.setdefault(searchTerms[j], []).append(i)
for element in itertools.product(*d.values()):
sortedList = sorted(list(element))
differenceList = [t - s for s, t in zip(sortedList, sortedList[1:])]
if min > sum(differenceList):
min = sum(differenceList)
sortedElement = sortedList
if sum(differenceList) == len(sortedElement) - 1:
break
try:
for i in range(sortedElement[0], sortedElement[len(sortedElement)-1]+1):
matchedString += "".join(stringList[i]) + " "
except:
pass
return matchedString
If anyone wants to clone my program here is code