# Finding the shortest excerpt that contains all search terms

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

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

## Pythonicity

Your solution feels very procedural and not really Pythonic. I believe that this function accomplishes the same task using roughly the same approach:

from itertools import product

words = document.split(" ")

search_term_positions = [
[i for i, word in enumerate(words) if word == term]
for term in search_terms
]

combos = [sorted(combo) for combo in product(*search_term_positions)]
if not combos:
return None    # Could not find all search terms
best_combo = min(combos, key=lambda combo: combo[-1] - combo[0])

return " ".join(words[best_combo[0] : best_combo[-1] + 1])


Observations:

• d is a variable name that suggests that it's a dict, but is not much more helpful than that. Instead of d.values(), I've defined search_term_positions, which is a much more descriptive variable name. You don't really even need a dictionary, since you only care about the values, not the keys.
• You can simplify the second for loop by taking full advantage of the built-in min() function.
• You wrote sum(differenceList) three times! sum(differenceList) is just sortedList[-1] - sortedList[0], because

$$(n_1 - n_0) + (n_2 - n_1) + (n_3 - n_2) + \ldots + (n_N - n_{N - 1})$$

is a telescoping series where all of the terms cancel except $-n_0$ and $n_N$.

• sortedElement[len(sortedElement)-1] can be written as sortedElement[-1].
• Swallowing all exceptions with except: pass is a no-no.

## Bugs

This function only recognizes words that are delimited by spaces. Any other punctuation could cause words to fail to be recognized.

Your algorithm works based on word count rather than by character positions. Therefore, you end up finding the excerpt with the fewest intervening words, which is not necessarily what I would consider to be the "shortest snippet". Example:

>>> answer('many google supercalifragilistic program to google a program', ['google', 'program'])


I've also written a different solution to solve the same problem. There, as here, I've made no attempt to choose a speedy algorithm, but rather aimed for clarity.

You can move a window (start,end) by increasing end as long as the window does not contain all terms, then increasing start as long the window contains all terms. This will find in linear time all possible windows containing all terms. Then take the shortest one.

Here is an implementation:

from collections import defaultdict

document = document.split(' ')  # document is converted to list of words
searchTerms = set(searchTerms)  # remove repeated searchTerms
start, end = 0, 0  # initial value for the sliding search window
d = defaultdict(int)  # occurence count of each searchTerm in the window (start, end)

best_window = (0, len(document))  # default answer if no solution is found
while True:
count = len([x for x in d.values() if x>0]) # number of searchTerms in the window (start, end)
if count == len(searchTerms):
# (start, end) is a window containing all search terms
if end - start < best_window[1] - best_window[0]:
# this window is the best, up to now
best_window = (start, end)
if document[start] in searchTerms:
# a search term is slipping out if we increase start
d[document[start]] -= 1
start += 1
else:
# the window does not contain all search terms
if end >= len(document):
# end of the story
break
if document[end] in searchTerms:
# a new search term will be included by increasing end
d[document[end]] += 1
end += 1
return ' '.join(document[best_window[0]:best_window[1]])

document = "a b c a c d b a"
searchTerms = ["a", "c", "d"]


• I'm glad you were able to finally figure it out. Commented Aug 31, 2015 at 6:45
• This algorithm failing many test cases. Commented Aug 31, 2015 at 6:45
• I really like your idea, I will work on it. Thanks Commented Aug 31, 2015 at 6:55
• I implemented your idea here and it is giving correct output link Commented Aug 31, 2015 at 19:35

I'll just make two notes about ways you should be handling Python since.

You're using for loops inefficiently. Python has the construct for var in iterable to make it easier to get each value from a collection object. So this

for j in range(len(searchTerms)):
for i in range(len(stringList)):
if searchTerms[j] == stringList[i]:


should be changed to this:

for term in searchTerms:
for s in stringList:
if term == s:


Never use a bare try except. By doing something like that, you could make this code run without issue.

try:
utterGibberish
except:
pass


From what I can see, you should only get an IndexError here, so you should just pass on that. You should always know what error is being passed over and not ignore unknown errors.

try:
for i in range(sortedElement[0], sortedElement[len(sortedElement)-1]+1):
matchedString += "".join(stringList[i]) + " "
except IndexError:
pass