如何降低python的時間複雜度？

-4

給出一段以空格分隔的小寫英文單詞和一列唯一的小寫英文關鍵字，找到其中包含按任意順序以空格分隔的所有關鍵字的最小字符串長度。如何降低python的時間複雜度？

我把下面的代碼錯誤在哪裏？我如何減少時間複雜度。

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))

來源

2017-10-05 rakesh kumar

這有一所學校分配的所有特徵。這些類型的問題通常不受歡迎。如果您要發佈代碼，請提供代碼無效的原因。謝謝。 – Torxed

@Toxxed - 無論其學校任務是否無關緊要，重要的是在[問]指導方針之後提出一個問題。 – Sayse

另外，由於問題是關於時間複雜度的，您能向我們展示您對時間複雜性的計算以及您的具體問題嗎？提示：你正在使用三個for循環，其中兩個循環要去'n' –

訣竅是掃描從左至右，一旦你找到一個包含所有鍵的窗口，儘量減少它在左，放大右側保留所有的條款都內的財產窗戶。

使用此策略，您可以在線性時間內解決任務。下面的代碼是我在弦數測試代碼的草案，希望評論足以彰顯最關鍵的步驟：

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

來源

2017-10-05 16:43:09

如何降低python的時間複雜度？

回答

相關問題