どのようにPythonの時間の複雑さを減らすには？

Question

空白で区切られた小文字の英単語の段落と一意の英小文字の英語のキーワードのリストを指定すると、任意の順序でスペースで区切られたすべてのキーワードが含まれている部分文字列の最小長が見つかります。

次のコードを挿入します。エラーはどこですか？どうすれば時間の複雑さを減らすことができますか？

import sys 
def minimumLength(text, keys): 
    answer = 10000000 
    text += " $" 
    for i in xrange(len(text) - 1): 
     dup = list(keys) 
     word = "" 
     if i > 0 and text[i - 1] != ' ': 
      continue 

     for j in xrange(i, len(text)): 
      if text[j] == ' ': 
       for k in xrange(len(dup)): 
        if dup[k] == word: 
         del(dup[k]) 
         break 
       word = "" 
      else: 
       word += text[j] 
      if not dup: 
       answer = min(answer, j - i) 
       break 

    if(answer == 10000000): 
     answer = -1 

    return answer 
text = raw_input() 
keyWords = int(raw_input()) 
keys = [] 
for i in xrange(keyWords): 
    keys.append(raw_input()) 
print(minimumLength(text, keys)) 

Answer 1

トリックは、左側にそれを削減し、すべての条件が内部に残る財産を維持し、右側にそれを拡大しようとするあなたはすべてのキーを含むウィンドウを見つけたら、右へ左からスキャンすることです窓。

この戦略を使用すると、タスクを線形時間で解決できます。

---

def minimum_length(text, keys): 
    assert isinstance(text, str) and (isinstance(keys, set) or len(keys) == len(set(keys))) 
    minimum_length = None 
    key_to_occ = dict((k, 0) for k in keys) 
    text_words = [word if word in key_to_occ else None for word in text.split()] 
    missing_words = len(keys) 
    left_pos, last_right_pos = 0, 0 

    # find an interval with all the keys 
    for right_pos, right_word in enumerate(text_words): 
     if right_word is None: 
      continue 
     key_to_occ[right_word] += 1 
     occ_word = key_to_occ[right_word] 
     if occ_word == 1: # the first time we see this word in the current interval 
      missing_words -= 1 
      if missing_words == 0: # we saw all the words in this interval 
       key_to_occ[right_word] -= 1 
       last_right_pos = right_pos 
       break 

    if missing_words > 0: 
     return None 

    # reduce the interval on the left and enlarge it on the right preserving the property that all the keys are inside 
    for right_pos in xrange(last_right_pos, len(text_words)): 
     right_word = text_words[right_pos] 
     if right_word is None: 
      continue 
     key_to_occ[right_word] += 1 
     while left_pos < right_pos: # let's try to reduce the interval on the left 
      left_word = text_words[left_pos] 
      if left_word is None: 
       left_pos += 1 
       continue 
      if key_to_occ[left_word] == 1: # reduce the interval only if it doesn't decrease the number of occurrences 
       interval_size = right_pos + 1 - left_pos 
       if minimum_length is None or interval_size < minimum_length: 
        minimum_length = interval_size 
       break 
      else: 
       left_pos += 1 
       key_to_occ[left_word] -= 1 
    return minimum_length