LeetCode 3. Longest Substring Without Repeating Characters
问题描述
给定一个字符串,找出最长不重复子串的长度。
栗 1:
栗 2:
栗 3:
解题思路
我的解法
主要思想
当第一眼看到这个题目时,条件反射的想起了动态规划,因为有“最长”二字。虽然答案并不是这种思路😆。
首先,考虑这道题时需要注意两个前提条件:
子串,即连续的字符。
子串中不能有重复的字符。
而以任意一个字符开始的子串都有可能是最长不重复的。如果我们可以记录以某个字符开始,且不重复子串的最大长度,那么便可求出结果。
当遍历字符时,虽然子串长度是不断增加的,但需要判断子串是否满足上述条件,来更新记录的长度值。
主要思想是,以数组 lenList
记录从某个字符开始的最长不重复子串的长度,即数组中第 i 个元素的值,对应着以 s[i]
开头的最长不重复子串长度,s
是给定的字符串。
当遍历到某字符(下标为 i)时,需要判断该字符能否新加到原子串中。而在它前面的字符([0, i-1]
)都有可能是子串的开始字符,所以需要逐个遍历更新长度。若可以,则更新长度值,即 lenList[j] = lenList[j+1] + 1
。
那么在什么情况下更新长度呢?比如遍历到第 i
个元素,要更新第 j
个元素的长度值,j < i
。
条件也很简单,如下:
当第
j
个元素与它后面的字符串(也就是[j+1, i]
区间的字符串)不重复时,则可更新。若有重复,那么则停止更新。因为不满足条件,而前一个字符的结果依赖于后一个字符,因此
[0, j]
范围内的字符都不需要更新了。
栗子详解
举个栗子,假设字符串为 pwwekew
。
当遍历到某个字符时,很显然,以该字符开始,到该字符为止的子串长度都为 1。
处理过程如下:
遍历字符
p
,此时lenList = [1]
。遍历字符
w
,前面有p
一个字符,而pw
是满足条件的子串,此时lenList = [2, 1]
。遍历字符
w
,前面有pw
两个字符,从后往前逐个遍历更新长度值。对于
w
,重复,停止更新,此时lenList = [2, 1, 1]
。
遍历字符
e
,前面有pww
三个字符,从后往前逐个遍历更新长度值。对于
w
,子串变为we
,lenList = [2, 1, 2, 1]
。对于
w
,由于它后面的字符串we
包含了w
,停止更新。最终,lenList = [2, 1, 2, 1]
。
遍历字符
k
,前面有pwwe
四个字符,逐个更新长度值。对于
e
,子串可为ek
,lenList= [2, 1, 2, 2, 1]
。对于
w
,子串可为wek
,lenList = [2, 1, 3, 2, 1]
。对于
w
,有重复,停止更新。
遍历字符
e
,前面有pwwek
五个字符,逐个更新长度值。对于
k
,子串可为ke
,lenList = [2, 1, 3, 2, 2, 1]
。对于
e
,ke
包含e
,停止更新。
遍历字符
w
,前面有pwweke
六个字符,逐个更新长度值。对于
e
,子串可为ew
,lenList = [2, 1, 3, 2, 2, 2, 1]
。对于
k
,子串可为kew
,lenList = [2, 1, 3, 2, 3, 2, 1]
。对于
e
,kew
包含e
,停止更新。
所以最终的结果为,lenList = [2, 1, 3, 2, 2, 2, 1]
,最长连续不重复子串的长度为 3。
js
代码如下:
更优解法
这种解法很巧妙,使用了滑动窗口的概念。在遍历过程中,不断更新左右边界值。
主要思想如下:
利用
map
记录字符的边界下标。当遍历到某字符时,若在
map
中已存在,则更新窗口的左边界为该字符的边界下标,从而可计算出包含不同字符的区间长度。
比如 abca
。map 中记录 a 的边界下标为 1
,那么在遍历到最后一个 a 时,区间长度为 3 - 1 + 1 = 3
。
注意:左边界更新时的取值应该是当前值与 map 中的值较大的那个。
比如 abba
。当遍历到最后一个 a 时, 左边界为 2
,而此时 map 中记录的值为 1。若直接取 map 中的值,则会计算错误。
js
代码如下:
版权声明: 本文为 InfoQ 作者【liu_liu】的原创文章。
原文链接:【http://xie.infoq.cn/article/c4d27b48715d4099b750d5ada】。文章转载请联系作者。
评论