python每日一题【剑指 Offer 48. 最长不含重复字符的子字符串】

day18-2022.11.12

题目信息来源
作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm
来源：力扣（LeetCode）

剑指 Offer 48. 最长不含重复字符的子字符串

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4
5
6
7
8
9
10
11

题解一：个人做题过程

这个方法是之前的连续子数组最大和，还有列表栈最大值的方法结合而来。空间复杂度比较高为2N，即$O(N)$，时间复杂度也为$O(N^2)$。设置 sub-s 保存最长子串，$dp[i]$ 保存前 i 个字符的最大连续子数字

如果下一个字符不在subs里，$dp[i]=dp[i-1]+1$，subs append（这里如果用字符串的话就是+，但是+就是重新创建了一个字符串，效率不高，所以换成了列表）。

如果下一个字符在subs里，就要找到重复字符的位置，把它和他之前的字符从subs里面pop出来，$dp[i]=len(subs)$。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        subs = [s[0]]
        dp = [0]*len(s)
        dp[0] = 1
        for i in range(1, len(s)):
            if s[i] not in subs:
                subs.append(s[i])
                dp[i] = dp[i-1] + 1
            else:
                while subs[0]!=s[i]:
                    subs.pop(0)
                subs.pop(0)
                subs.append(s[i])
                dp[i] = len(subs)
        return max(dp)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

查看了解析，考虑到我这里的空间复杂度却有可优化之处，便有下面简化版本：

链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5dz9di/

空间复杂度降低：
由于返回值是取 $dp$ 列表最大值，因此可借助变量 tmp存储 $dp[j]$，变量 $maxlen$ 每轮更新最大值即可。
此优化可节省 $dp$ 列表使用的 $O(N)$ 大小的额外空间。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        subs = [s[0]]
        max_len = 1
        tmp = 1
        for i in range(1, len(s)):
            if s[i] not in subs:
                subs.append(s[i])
                tmp = tmp + 1
            else:
                while subs[0]!=s[i]:
                    subs.pop(0)
                subs.pop(0)
                subs.append(s[i])
                tmp = len(subs)
            max_len = max(max_len, tmp)
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

那还可不可以继续优化呢？题解方式在问题分析上其实和我是一样的，如果没有重复，就+1，有重复就从重复的那个字母的地方开始重新计算dp。我的方式是通过保存计算subs的长度来计算dp的。看到解析，似乎可以考虑有另外一个下标来存储重复字母的前一个序号。

但是还有问题：重复的字母可能在subs队列的中间，所以不能通过记录像窗口的端首端尾一样，记录首尾的指针。并且，不可能只有某一个字母重复，所以可以考虑，记录每个字母出现的位置。遍历查看是否有这个字符，有的话，更新字母的位置，同时更新dp值。这种一一对应的存储关系，可以用字典。而这样的存储，是和 s 的长度无关的，所以空间复杂度是 $O(1)$。继续优化一下代码，就可以得到官方题解里的 动态规划+哈希表法

下面是哈希表的第一版，其实有一个bug，就是如果重复的字母已经不在字串里了，还是会被算了，所有还需要判断一下字串的区间

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        # 存储所有出现字母的字典
        mydict = {}
        # 初始化
        max_len = 1
        tmp = 1
        mydict[s[0]] = 0
        for i in range(1, len(s)):
            value = mydict.get(s[i])
            if value==None:
                tmp = tmp + 1
            else:
                tmp = i - value
            # 更新新的序号
            mydict[s[i]] = i
            max_len = max(max_len, tmp)
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

修改一下为

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s:return 0
        # 存储所有出现字母的字典
        mydict = {}
        # 初始化
        max_len = 1
        tmp = 1
        mydict[s[0]] = 0
        for i in range(1, len(s)):
            value = mydict.get(s[i])
            if value==None:
                tmp = tmp + 1
            elif tmp>=i-value:
                tmp = i - value
            else:
                tmp = tmp + 1
            # 更新新的序号
            mydict[s[i]] = i
            max_len = max(max_len, tmp)
        return max_len
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

value部分的不同条件还可以简化一下：

            if value!=None and tmp>=i-value:
                tmp = i - value
            else:
                tmp = tmp + 1
1
2
3
4

也可以是

            value = mydict.get(s[i], -1)
            if tmp>=i-value:
                tmp = i - value
            else:
                tmp = tmp + 1
1
2
3
4
5