优化蛮力方法以最长的子字符串而无需重复字符 [英] Optimizing brute force approach to Longest Substring Without Repeating Characters

问题描述

我正在尝试通过解决LeetCode上的一些问题来改进我的Python.

I'm trying to improve my Python by solving some problems on LeetCode.

我目前正在处理最长的不重复字符的子字符串问题:

给出一个字符串，找到最长子字符串的长度，而不重复字符.

Given a string, find the length of the longest substring without repeating characters.

示例1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

示例2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

示例3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

我正在尝试通过查找所有子字符串然后找到最长的子字符串来进行暴力破解:

I am trying to do brute forcing, by finding all substrings and then finding the longest one:

def lengthOfLongestSubstring(self, s: str) -> int:
        list_of_values = [0]
        if (not s):
            return 0

        new_list = list(s[0])
        i = 1
        size_s = len(s)
        while i < size_s:
            if s[i] not in new_list:
                new_list.append(s[i])
                i += 1
            else:
                list_of_values.append(len(new_list))
                new_list = []
                s = s[1:]
                i = 0
                size_s = len(s)
                if size_s < max(list_of_values):
                    break
        return max(max(list_of_values), len(new_list))

该解决方案有效，但是在LeetCode上的最后一个测试用例(很长的字符串)上超时.有没有人建议如何使它更快?

The solution works, but it times out for the last test case on LeetCode (a very long string). Does anyone have suggestions on how to make this faster?

推荐答案

这些只是该算法的一些提示.

These are just some hints for the algorithm.

您可以为首个字母设置两个指针"

You can set two "pointers" to the first letter,

abcabcbb
^start
^end

然后前进end指针并将字母放入哈希图或其他东西中，以便在前进时可以有效地检查重复的字母.重复一遍，

then you advance the end pointer and put the letters in a hashmap or somthing, so you can efficiently check for repeated letters when you advance. As soon as you get a repetition,

abcabcbb
^start
   ^end

将两个位置和长度保存在列表或元组中，然后前进start直到不再有重复的字母

you save the two positions and the length in list or tuple, and then you advance start until there are no more repeated letters

abcabcbb
 ^start
   ^end

然后，您仅在长度增加时才覆盖两个保存的位置和长度，从而再次开始前进end，重复该过程.

Then you start advancing end again, repeating the process, by overriding the two saved positions and the length only if the lenght increases.

您应该以遇到的最后一个最长子字符串的开始和结束位置结尾，在这种情况下，为bcb

You should end up with the start and end positions of the last longest substring you met, in this case bcb

abcabcbb
    ^start
      ^end

请注意，这是最后一个，其他有效的候选项是abc，bca，依此类推.

Note that it is the last, and other valid candidates are abc, bca, and so on.

这篇关于优化蛮力方法以最长的子字符串而无需重复字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！