如何降低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的时间复杂度？

回答

相关问题