这是一个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())
我知道有其他的解决方案来解决我的问题,但我相信我的会工作,如果我能找到如何解决这个问题。
1条答案
按热度按时间rjee0c151#
您有效地回答了自己的问题。您的方法要求您在每次遇到重复时都往回翻一翻。但是在重置计数之前,您没有递减
i
来完成这一操作。您需要往回扫描字符串,并从运行开始的位置之后重新开始。一些评论:
elif
线可以仅仅是else
,因为它是if
条件的精确否定。这取决于我们计算的是什么!
in
运算符可以在恒定时间内实现,并且具有合理的内存,并且知道我们不会存储重复的字符。因此,我们假设我们已经这样做了,忽略现在实现的该运算符的实际成本,只关注我们需要调用它多少次。这给出了算法复杂度的合理近似值。(出于以下目的,我将删除
elif
子句中的冗余检查,并将其命名为Alg.1
)当算法向前遍历字符串时,它会为每个字符调用
in
,但当需要回溯时,它也会重复这些检查。回溯会根据所涉及的字符串添加不同数量的操作。示例:
abcabcbb
要求您的算法检查字符串中某个字符是否存在25次;而pwwkew
需要12次检查。曾经有一个算法作为答案发布,但似乎已经消失了。它天真地检查所有从每个位置开始的子字符串,直到找到重复的为止。所以它遍历字符串的效率有点低。让我们称之为
Alg.2
。相比之下,下面的算法对输入中的每个字符执行一次
in
运算,并对当前最长子字符串的开头和重复字符之间的每个字符再执行一次in
运算。如果我们生成许多(我做了10000个)27个字符(首先保证重复)和1000个字符(强调任何低效率)的随机字符串,然后计算每个算法对
in
操作符的调用,我们得到平均操作计数:还包括设计为对每个算法不利的场景的操作数。