无重复字符的最长子串

003_longest_substring_without_repeating_characters

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

示例:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。

1.掐头法&

第一反应是简单的掐头法(不知道叫啥),用list存substring,往list尾部放字符,有重复的就从头部把重复的去掉

stackoverflow上很多都推荐用enumerate替代for-in range写法,以后可以试试,用leetcode-cn平台测下来注释里那几种写法都差不多

hist:

  • 最初写的时候没有最后的那个判断,导致全不重复时会出问题
class Solution:
    def lengthOfLongestSubstring(self, s: 'str') -> 'int':
        list = []
        result = 0
        for i in range (len(s)):
          # for i,_ in enumerate(s):
          # for char in s:
            if s[i] not in list:
                list.append(s[i])
            else :
                if len(list)>result:
                    result =len(list)
                # result = max(len(list),result)
                list.append(s[i])
                list = list[list.index(s[i])+1:]

        if len(list) > result:
            result = len(list)
        # result = max(len(list),result)
        return  result
108ms 6.6MB 76.79% 87%

2. 字典备忘录~

还是来一波dict,python里用dict经常有惊喜,应该是HashTable的原因

感觉dict解题都是遍历,再把已遍历的放进dict里面,类似备忘录,方便查询.

class Solution:
    def lengthOfLongestSubstring(self, s: 'str') -> 'int':
        last_seen = {}
        p = 0
        result = 0
        for i, c in enumerate(s):
            if c in last_seen and last_seen[c] >= p:
                p = last_seen[c]+1
            else:
                result = max(result, i-p+1)
            last_seen[c] = i
        return result
84ms 6.6MB 99.32% 99.65%

3.暴力

官方题解里居然还有暴力法…O(n^3)的时间 太丑了就不写了

本文总字数: 1009