Leetcode 3

Posted on | | 阅读数
Words count in article: 201 | Reading time ≈ 1

Question

Solution1

比较暴力的方法。从i开始，遍历i+1之后的元素并且添加到dict里面。如果出现重复，则记录当前dict的长度，并清空当前dict。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:
            return 0
        dictt = {}
        maxx = 1
        for i in range(len(s)-1):
            dictt[s[i]] = 1
            for j in range(i+1, len(s)):
                if s[j] not in dictt:
                    dictt[s[j]] = 1
                    maxx = max(maxx, len(dictt))
                else:
                    dictt.clear()
                    break
        return maxx

Solution2

改进版本。假设出现重复元素a，则将start设为a后第一个元素的index，然后重置dictt里面a的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if len(s) < 2:
            return len(s)
        n = len(s)
        dictt, start, results = {}, 0, 0
        for i, elem in enumerate(s):
            if elem in dictt:
                results = max(results, i - start)
                start = max(start, dictt[elem]+1)
            dictt[elem] = i
        
        return max(results, len(s)-start)