[Leetcode题解]无重复字符的最长子串

无重复字符的最长子串image.png

这个题很容易想到是使用哈希表,当遍历每个字符的时候,查找之前是否出现过,这个题细节较多,比较容易出错。

1.建立一个字典,保存每个字符最后的下标
2.使用一个start记录当前不重复子字符串的开始位置。这一点很重要。初始化start = 0
2.从前往后遍历,判断当前字符是否当前不重复子字符串中出现过。如果出现过则,更新当前不重复子字符串,start变为重复位置的下一个。同时不要忘记记录当前字符的位置

    if ch in d and d[ch]>=start:
         start = d[ch] + 1
         d[ch] = index

3.如果出现过了,则判断当前位置和字符串开始位置的距离,并且更新最大距离。

      else:
          ans = max(index-start+1, ans)
          d[ch] = index

这里我错误了好多次,我觉得是我没有把握住“当前不重复子字符串”这一关键,考虑了过多。完整代码如下:

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        # 保存各个字符的Index
        d = {}

        start,ans = 0,0

        for index,ch in enumerate(s):
            if ch in d and d[ch]>=start:
                start = d[ch] + 1
                d[ch] = index
            else:
                ans = max(index-start+1, ans)
                d[ch] = index

        return ans

评论

暂无评论