无重复字符的最长子串Python3

45次阅读

共计 544 个字符,预计需要花费 2 分钟才能阅读完成。

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

示例:”abbcc” –> “ab” or “bc”、”abcadef” –> “adef”

解决思路:使用蛮力算法算法很容易实现,但是时间复杂度为 O(n^2)。本题可以通过一次遍历完成,比如 ”abcadef”,正常遍历,如果当前遍历字符不在字符串中,将它添加至字符串;当遍历到第 2 个 a 时,发现重复,此时截取第 1 个 a 后的第一个字符开始到第 2 个 a 为新字符串,并比较最大长度,依此类推。

a –> ab –> abc - a 重复 -> bca –> bcad –> bcade –> bcadef

代码如下 (~▽~):

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) == 0:
            return 0
        st = ''
        length = 0
        for i in range(len(s)):
            if s[i] not in st:
                st+=s[i]
                length=length if(length>len(st)) else len(st)
            else:
                st = st[st.find(s[i])+1:] + s[i]
        return length

时间与空间复杂度占用:

原题链接:https://leetcode-cn.com/probl…

正文完
 0