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, sortedElement[len(sortedElement)-1]+1): matchedString += "".join(stringList[i]) + " " except: pass return matchedString
If anyone wants to clone my program here is code