Leetcode3. 无重复字符的最长子串 Python实现

  • 题目要求:

image.png

  • 思路

    • 用一个字典来存数组元素的index
    • 记录一个start,用来表示当前的不重复的字符串的起点
    • 定义mymax,保存当前遍历过的最长的字符串的长度
    • 遍历数组,如果元素i不在字典中,说明当前没有出现重复的字符,如果i的下标-start大于mymax,也就是当前不重复的字符串的长度大于保存的最长的长度,更新mymax的值,如果元素i在字典中,说明前面已经有重复的元素,把字典中mymax[i]的值赋给start,更新mymax[i]为当前的下标。比如字符串abhwb,遍历到第二个b时,当前不重复的字符串是从上一次出现的b的下一位到当前的b,所以要先把mymax[i]的值赋给start。
  • 核心代码:
mydict = {}
mymax = 0
# start从-1开始是因为有一个特殊的测试用例" ",需要返回的值是1
start = -1

for i in range(len(s)):
    # 如果遍历到的元素在字典中,说明重复出现了,而且如果这个值上一次出现的位置在start后面,start需要更新
    if s[i] in mydict and mydict[s[i]] > start:
        #字典中旧的值赋给start,即上一次该元素出现的位置,更新字典中这个元素当前的位置
        start , mydict[s[i]] = mydict[s[i]] , i  
    else:
        #如果不在字典中,把这个值加到字典里,value为该元素的下标
        mydict[s[i]] = i
        # i - start为当前无重复的字符串的长度,如果这个长度比记录的最长的值mymax还大,更新mymax
        if i - start > mymax:
            mymax = i - start

return mymax
  • 完整代码:
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        mydict = {}
        mymax = 0
        start = -1

        for i in range(len(s)):
            if s[i] in mydict and mydict[s[i]] > start:
                start , mydict[s[i]] = mydict[s[i]] , i  
            else:
                mydict[s[i]] = i
                if i - start > mymax:
                    mymax = i - start

        return mymax
  • 解释2:

    • 用一个字典来保存所有遍历过的字符及字符出现的下标,一个start用来标识当前不重复子串起点的前一个位置,一个res用来表示结果(子串的最大长度)
    • 从头开始遍历这个字符串,如果遇到不在字典中的字符,就把这个字符及下标记录到字典中,如果当前的index-start,也就是不重复子串的长度比res大,那么把当前不重复子串的长度赋给res
    • 如果遇到在字典中的字符,且这个字符上一次出现的下标大于start的当前位置,那么把这个位置赋给start(也就是start只向后移动),再把字典里的这个字符对应的下标更新
    • 最后返回结果res
  • 核心代码
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # start标志不重复子串的前一个位置
        start = -1
        # 字典,用来保存字符及字符上一次出现的下标
        d = {}
        # 不重复子串的最大长度
        res = 0
        # 遍历字符串
        for i in range(len(s)):
            # 字符在字典中,且start不往回走
            if s[i] in d and d[s[i]] > start:
                start = d[s[i]]
                d[s[i]] = i
            # 字符不在字典中
            else:
                d[s[i]] = i
                # 也可以写成 res = max(res, i - start)
                if i - start > res:
                    res = i - start
        return res
  • 完整代码:
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        start = -1
        d = {}
        res = 0
        for i in range(len(s)):
            if s[i] in d and d[s[i]] > start:
                start = d[s[i]]
                d[s[i]] = i
            else:
                d[s[i]] = i
                if i - start > res:
                    res = i - start
        return res

评论

暂无评论