无重复字符的最长子串 - python

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

  这道算法题目属于中等难度,但对于弱小的我来说还是太难了,在一开始看到这道题的时候还觉得挺简单的,慢慢的深入进去发现并不简单,只能说我并没有解决该道算法题,先说一下我自己写的吧!

class Solution:
    def lengthOfLongestSubstring(self, s):
        n = 0
        list1 = [] # 用来存放已经读取过的字符
        list2 = [] # 用来记录每一步的最大值
        for i in s:
            if i not in list1:
                n += 1
                list1.append(i) # 将记录到的字符添加进 list1
                list2.append(n) # 将每一步记录的长度放入 list2中
            else:
                list1 = []  # 如果遇到了重复的就将列表置为空
                list1.append(i)
                n = 1

        return max(list2)

结果就是,能通过测试,但无法通过大部分情况。如abcadcea 输出的结果应该为4 但是为3

在这里贴一下大神的代码吧

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        st = {}
        i, a = 0, 0
        for j in range(len(s)):
            if s[j] in st:
                i = max(st[s[j]], i)
            a = max(a, j - i)
            st[s[j]] = j + 1
        return a

真的就是神代码,花了我挺久时间才看懂,果然还是我太菜了 

点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

Title - Artist
0:00