3. 无重复字符的最长子串
题目描述提示帮助提交记录社区讨论阅读解答
随机一题
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其
长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b"
,其长度为 1。
示例 3:
输入: "pwwkew" 输出: 3 解释: 无重复字符的最长子串是"wke"
,其长度为 3。请注意,答案必须是一个子串,"pwke"
是一个子序列 而不是子串。
思路:
采用切分的方式,遇到重复字符时,记录无重复字符的长度,把前面的所有字符串“丢掉”然后以这个起点重新开始做切分,再遇到相同字符得到的长度与前面对比,取最大值,往复的到。
class Solution:def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""d = {}start = 0ans = 0for i,c in enumerate(s):if c in d:start = max(start, d[c] + 1)print("start:",start)d[c] = iprint("d:",d)ans = max(ans, i - start + 1)print("ans:",ans)return ans
if __name__=='__main__':a = Solution()s = str('pwwkew')ans = a.lengthOfLongestSubstring(s)print(ans)d: {'p': 0}
ans: 1
d: {'p': 0, 'w': 1}
ans: 2
start: 2
d: {'p': 0, 'w': 2}
ans: 2
d: {'p': 0, 'w': 2, 'k': 3}
ans: 2
d: {'p': 0, 'w': 2, 'k': 3, 'e': 4}
ans: 3
start: 3
d: {'p': 0, 'w': 5, 'k': 3, 'e': 4}
ans: 3
3Process finished with exit code 0
更多推荐
长子,字符,leetcode
发布评论