时间戳

首页 > 解决方案 > 查找所有子字符串和时间限制超出错误

python - 查找所有子字符串和时间限制超出错误

问题描述

我想找到包含所有字母的最短子字符串。我找到了所有子字符串并检查了它们。它的运行时间很长，并且出现了超出时间限制的错误。我认为这个算法不是最优的。

  1. 如果有更有效的算法，请教我。
  2. 为什么我收到超出时间限制的错误？我认为这是因为嵌套的 for 循环。

我有一个函数'pan'来检查字符串是否有每个字母。

text_list = []
len_list = []

for start in range(len(text) - 1):
    for stop in range(start + 26, len(text)):
        if pan(text[start:stop + 1]):
            text_list.append(text[start:stop + 1])
            len_list.append(len(text[start:stop + 1]))
            break # finding shortest one

if not text_list:
    result = None
else:
    # to find shortest length.
    index = len_list.index(min(len_list))
    result = text_list[index]

标签： pythonalgorithm

解决方案

您的性能问题是，对于每个开始，每个结束，您都要重新计算字母表。奇怪的是，这已经是O(n^3)并且取决于你是怎么做pan的，也许更糟。只要把它扔到一个中间有一百万次'a'的字符串上，你就会遇到性能问题。

这是另一种方法。在字典中保留一个窗口和当前字母计数。虽然不需要第一个字母，但将窗口的开头向前滑动，看看我们是否改进了。如果是，将末端向前滑动。此更新是O(1)每次迭代，我们迭代一次将每个字母放入窗口，一次将其移出。所以这个策略是O(n)。

这是此策略的代码。

def shortest_alphabet_substring(text, alphabet='abcdefghijklmnopqrstuvwxyz'):
    in_alphabet = set(list(alphabet))
    best_start = None
    best_size = None
    char_count = {}

    # Find starting window
    start = size = 0
    while size < len(text) and len(char_count) < len(in_alphabet):
        c = text[size]
        if c not in in_alphabet:
            pass
        elif c in char_count:
            char_count[c] = 1 + char_count[c]
        else:
            char_count[c] = 1
        size = size + 1

    if len(char_count) == len(alphabet):
        best_start = start
        best_size = size
        while start + size <= len(text):
            start_c = text[start]
            if start_c not in alphabet or 1 < char_count[start_c]:
                # Slide the window forward
                if start_c in alphabet:
                    char_count[start_c] = char_count[start_c] - 1
                start = start + 1
                size = size - 1
                # Did we improve on our best?
                if size < best_size:
                    best_start = start
                    best_size = size
            else:
                # widen the window
                end_c = text[start + size - 1]
                size = size + 1
                if end_c in in_alphabet:
                    char_count[end_c] = char_count[end_c] + 1
        return text[best_start: best_start + best_size]
    return None

推荐阅读