欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

3无重复字符的最长子串

程序员文章站 2022-06-10 22:26:55
...

3无重复字符的最长子串
方法一:滑动窗口
以每个字符为开头,寻找无重复字符的最长子串

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        if not s:
            return 0
        start = 0
        res = 0
        for i in range(len(s)):
            if not self.isUnique(s[start:i+1]):
                start+=1
            elif res < i+1-start:
                res = i+1-start
        return res

    def isUnique(self,s):
        strList = list(s)
        for i in range(len(s)):
            if s.count(strList[i]) != 1:
                return False
        return True

方法二:滑动窗口改进
实际上,没有必要寻找以每个字符开头的子串,从重复的字符开始寻找可以节约时间

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        substr = {}
        i,res = 0,0
        for j in range(len(s)):
            if s[j] in substr:
                i = max(substr[s[j]],i)
            res = max(res,j-i+1)
            substr[s[j]] = j+1
        return res
相关标签: LeetCode习题