7
\$\begingroup\$

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

\$\endgroup\$

3 Answers 3

4
\$\begingroup\$

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

def answer(document, search_terms):
    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'])
'google supercalifragilistic 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.

\$\endgroup\$
0
3
\$\begingroup\$

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

def answer(document, searchTerms):
    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"]

print answer(document, searchTerms)
\$\endgroup\$
4
  • \$\begingroup\$ I'm glad you were able to finally figure it out. \$\endgroup\$
    – ErikR
    Aug 31, 2015 at 6:45
  • \$\begingroup\$ This algorithm failing many test cases. \$\endgroup\$
    – python
    Aug 31, 2015 at 6:45
  • \$\begingroup\$ I really like your idea, I will work on it. Thanks \$\endgroup\$
    – python
    Aug 31, 2015 at 6:55
  • \$\begingroup\$ I implemented your idea here and it is giving correct output link \$\endgroup\$
    – python
    Aug 31, 2015 at 19:35
3
\$\begingroup\$

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
\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.