[Leetcode][python]Longest Substring Without Repeating Characters/无重复字符的最长子串
[Leetcode][python]Longest Substring Without Repeating Characters/无重复字符的最长子串
蛮三刀酱
发布于 2019-03-26 17:05:53
发布于 2019-03-26 17:05:53
题目大意
给定一个字符串，从中找出不含重复字符的最长子串的长度。 例如，”abcabcbb”的不含重复字母的最长子串为”abc”，其长度是3。”bbbbb”的最长子串是”b”，长度为1。
解题思路
哈希表+双指针
来自博客
变量start和end分别记录子串的起点和终点，从左向右逐字符遍历原始字符串，每次将end + 1，字典countDict存储当前子串中各字符的个数 当新增字符c的计数 > 1时，表明已经有重复，向右移动起点start，并将s[start]在字典中的计数 - 1，直到countDict[c]不大于1为止更新最大长度
代码
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
ans, start, end = 0, 0, 0
countDict = {}
for c in s:
end += 1
countDict[c] = countDict.get(c, 0) + 1 # countDict.get(c, 0)意思是：若c不存在直接返回0
while countDict[c] > 1:
countDict[s[start]] -= 1
start += 1
ans = max(ans, end - start)
return ans优化思路：遇到重复的字母，直接跳到重复字母的后面一个，而不是像之前那样慢慢向右移动！
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
used = {}
max_length = start = 0
for i, c in enumerate(s):
if c in used and start <= used[c]:
start = used[c] + 1
else:
max_length = max(max_length, i - start + 1)
used[c] = i
return max_length总结
- countDict.get(c, 0)
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年08月08日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录