Skip to content

Instantly share code, notes, and snippets.

@rakeshsukla53
Created August 31, 2015 05:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save rakeshsukla53/7dad6b8fe1618803f201 to your computer and use it in GitHub Desktop.
Save rakeshsukla53/7dad6b8fe1618803f201 to your computer and use it in GitHub Desktop.
time complexity of the program
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment