python 找到最长的没有重复字符的子字符串,我的代码在一半的测试用例中有效,我如何改变它,使它每次都有效

juud5qan  于 2023-01-01  发布在  Python
关注(0)|答案(1)|浏览(88)

这是一个leetcode问题:给定一个字符串s,求不含重复字符的最长子串的长度。
实施例1:
输入:s =“abcabcbb”输出:3说明:答案为“abc”,长度为3,示例2:
输入:s =“pwwkew”输出:3说明:答案是“wke”,长度为3。注意答案必须是子串,“pwke”是子序列而不是子串。
我的代码在遇到以下字符串时失败:s =“数字视频文件”
我知道问题是什么,但我只是不能编码使它工作.我知道我的程序将不会从“v”星星后,字符得到重置,并将从“d”开始,但我不知道热使它这样做.这是我的代码:

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        substring_length = {}
        i = 0
        count = 0
        char = ""
        while i != len(s) :
            if s[i] not in char:
                char = char + s[i]
                count += 1
                i += 1
                if i == len(s) :
                    substring_length[char] = count
            elif s[i] in char:
                substring_length[char] = count
                char = ""
                count = 0
            
        if len(substring_length) == 0:
            substring_length[s] = len(s)
        return max(substring_length.values())

我知道有其他的解决方案来解决我的问题,但我相信我的会工作,如果我能找到如何解决这个问题。

rjee0c15

rjee0c151#

您有效地回答了自己的问题。您的方法要求您在每次遇到重复时都往回翻一翻。但是在重置计数之前,您没有递减i来完成这一操作。您需要往回扫描字符串,并从运行开始的位置之后重新开始。

elif s[i] in char:
                substring_length[char] = count
                char = ""
                i -= (count - 1)
                count = 0

一些评论:

  • elif线可以仅仅是else,因为它是if条件的精确否定。
  • 正如你所说,这个问题还有其他的解决方案,如果你避免回溯,那么你会得到一个更快的结果。
  • (编辑以讨论效率-评论部分空间不足或格式设置能力不足)*
    • 但是我的程序不是仍然是O(n)吗。所以它会和滑动窗口方法一样快吗?**

这取决于我们计算的是什么! in运算符可以在恒定时间内实现,并且具有合理的内存,并且知道我们不会存储重复的字符。因此,我们假设我们已经这样做了,忽略现在实现的该运算符的实际成本,只关注我们需要调用它多少次。这给出了算法复杂度的合理近似值。
(出于以下目的,我将删除elif子句中的冗余检查,并将其命名为Alg.1
当算法向前遍历字符串时,它会为每个字符调用in,但当需要回溯时,它也会重复这些检查。回溯会根据所涉及的字符串添加不同数量的操作。
示例:abcabcbb要求您的算法检查字符串中某个字符是否存在25次;而pwwkew需要12次检查。
曾经有一个算法作为答案发布,但似乎已经消失了。它天真地检查所有从每个位置开始的子字符串,直到找到重复的为止。所以它遍历字符串的效率有点低。让我们称之为Alg.2
相比之下,下面的算法对输入中的每个字符执行一次in运算,并对当前最长子字符串的开头和重复字符之间的每个字符再执行一次in运算。

def lengthOfLongestSubstring(self, s: str) -> int:
        currentSubstring = ""
        longestSubstring = s[0]
        for i in s:
            if len(longestSubstring) < len(currentSubstring):
                longestSubstring = currentSubstring
            while i in currentSubstring:
                currentSubstring = currentSubstring[1:]
            currentSubstring += i
        if len(longestSubstring) < len(currentSubstring):
            longestSubstring = currentSubstring
        return len(longestSubstring), longestSubstring

如果我们生成许多(我做了10000个)27个字符(首先保证重复)和1000个字符(强调任何低效率)的随机字符串,然后计算每个算法对in操作符的调用,我们得到平均操作计数:

Alg.#  Ops for 27 chars  Ops for 1000 chars  Ops for 'a..za'  Ops for abab..aba  Ops for aabb..zzaa
Alg.1      145               7032                 53              77                 132
Alg.2      165               7053                378              78                 132
Alg.3       48               1994                 28              52                 105

还包括设计为对每个算法不利的场景的操作数。

相关问题