[LeetCode] Longest Substring Without Repeating Characters

题意

给一个字符串,求它的最长不重复子串的长度。

题解

第一想法:DP,我不会。

第二想法:DP,我不会……

然后慢慢想:假设现在前面已经处理过一些字符串了,现在来到了第 i 个字符处。最简单的情况,如果这个字符在前面已经处理过的字符串中没有出现过,怎么办?直接 extend 进去,当前长度 + 1,然后把这个字符最后出现的位置记录下来。

如果这个字符之前出现过,怎么办?这里就要分成两种情况了。我直接画图说明吧。图中 | 代表当前不重复的字符串,+ 代表当前字符,o 代表这个字符上一次出现的位置。

第一种情况:

这种情况下,就要缩短不重复字符串的长度了。新的不重复字符串是从 o 后面一个字符开始,到当前字符 + 截止。

第二种情况:

也就是说,重复点不在当前不重复字符串内。那么好啊,对于当前不重复字符串来说,字符 + 没有出现过。直接 extend,长度 + 1。

还有其他情况了么?没有了。

如果硬要用 DP 数组记录下来上面的 “长度” 信息的话,那么 f 数组的含义是 “以第 i 个字符为结尾的最长不重复字符串的长度”。这样说清楚么?

下面一个问题,字符 + 之前在那儿出现过,怎么记录?

字典啊!别忘了你现在用的是 Python!字典的查找可是 $O(1)$ 级别的运算啊!

代码

结果

982 / 982 test cases passed.
Status: Accepted
Runtime: 124 ms

982 个测试点…… 也是丧心病狂啊!

其他解法

如果你崇尚暴力…… 那就暴力着来吧:枚举起点、终点,截取字符串,看看有没有重复的字符,有的话就丢掉,没有的话比较长度。时间大概是 $O(n^3)$ 。

如果你不想那么暴力…… 还可以温柔一点:枚举起点、终点,看看有没有重复的字符,有的话就丢掉,没有的话记录最大长度。然后继续枚举起点的时候,长度至少比当前最大长度要长。时间大概也是 $O(n^3)$ 。

有人说,用滑动窗口:维护一个不重复子串窗口,新来一个字符,在窗口内判重,不重就增加窗口长度,重复就把重复点之前的东西全删除。其实和我的想法是一样的。不过这个做法时间接近 $O(n^2)$ 了。不太划算。

还有各种 DP 的方案我就看不懂了……

桩程序

发表评论

电子邮件地址不会被公开。 必填项已用*标注