[Leetcode题解]无重复字符的最长子串
文章目录
无重复字符的最长子串
这个题很容易想到是使用哈希表,当遍历每个字符的时候,查找之前是否出现过,这个题细节较多,比较容易出错。
1.建立一个字典,保存每个字符最后的下标
2.使用一个start记录当前不重复子字符串的开始位置。这一点很重要。初始化start = 0
2.从前往后遍历,判断当前字符是否当前不重复子字符串中出现过。如果出现过则,更新当前不重复子字符串,start变为重复位置的下一个。同时不要忘记记录当前字符的位置
if ch in d and d[ch]>=start:
start = d[ch] + 1
d[ch] = index
3.如果出现过了,则判断当前位置和字符串开始位置的距离,并且更新最大距离。
else:
ans = max(index-start+1, ans)
d[ch] = index
这里我错误了好多次,我觉得是我没有把握住“当前不重复子字符串”这一关键,考虑了过多。完整代码如下:
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
# 保存各个字符的Index
d = {}
start,ans = 0,0
for index,ch in enumerate(s):
if ch in d and d[ch]>=start:
start = d[ch] + 1
d[ch] = index
else:
ans = max(index-start+1, ans)
d[ch] = index
return ans
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论