LeetCode 3. Longest Substring Without Repeating Characters

用户头像
liu_liu
关注
发布于: 2020 年 07 月 08 日
LeetCode 3. Longest Substring Without Repeating Characters

问题描述



给定一个字符串,找出最长不重复子串的长度。



栗 1:

输入:"abcabcbb"
输出:3
解释:
abc 是最长的不重复子串。



栗 2:

输入:"bbbbb"
输出:1
解释:
子串为 b。



栗 3:

输入:"pwwkew"
输出:3
解释:
子串为 wke。



想看英文原文的戳这里



解题思路

我的解法

主要思想



当第一眼看到这个题目时,条件反射的想起了动态规划,因为有“最长”二字。虽然答案并不是这种思路😆。



首先,考虑这道题时需要注意两个前提条件:

  • 子串,即连续的字符。

  • 子串中不能有重复的字符。



而以任意一个字符开始的子串都有可能是最长不重复的。如果我们可以记录以某个字符开始,且不重复子串的最大长度,那么便可求出结果。



当遍历字符时,虽然子串长度是不断增加的,但需要判断子串是否满足上述条件,来更新记录的长度值。



主要思想是,以数组 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,子串变为 welenList = [2, 1, 2, 1]

  • 对于 w,由于它后面的字符串 we 包含了 w,停止更新。最终, lenList = [2, 1, 2, 1]



  • 遍历字符 k,前面有 pwwe 四个字符,逐个更新长度值。

  • 对于 e,子串可为 eklenList= [2, 1, 2, 2, 1]

  • 对于 w,子串可为 weklenList = [2, 1, 3, 2, 1]

  • 对于 w,有重复,停止更新。



  • 遍历字符 e,前面有 pwwek 五个字符,逐个更新长度值。

  • 对于 k,子串可为 kelenList = [2, 1, 3, 2, 2, 1]

  • 对于 eke 包含 e,停止更新。



  • 遍历字符 w,前面有 pwweke 六个字符,逐个更新长度值。

  • 对于 e,子串可为 ewlenList = [2, 1, 3, 2, 2, 2, 1]

  • 对于 k,子串可为 kewlenList = [2, 1, 3, 2, 3, 2, 1]

  • 对于 ekew 包含 e,停止更新。



所以最终的结果为,lenList = [2, 1, 3, 2, 2, 2, 1],最长连续不重复子串的长度为 3。



js 代码如下:

var lengthOfLongestSubstring = function (s) {
// 存到以某个位置字符开始的最大长度
let lenList = []

// 最大长度
let longestLen = 0
let i = 0
while (i < s.length) {
// 当前元素开始的长度肯定为 1
lenList.push(1)

if (longestLen < 1) {
longestLen = 1
}

// 遍历list,更新最大值
let j = i - 1

while (j >= 0) {
// [j+1,i] 的子串
const substr = s.substr(j + 1, i - j)

// 是否包含字符
if (!substr.includes(s[j])) {
lenList[j] = lenList[j + 1] + 1

// 记录最大值
if (longestLen < lenList[j]) {
longestLen = lenList[j]
}
} else {
// 停止更新
break
}

j -= 1
}

i += 1
}

return longestLen
};



更优解法



这种解法很巧妙,使用了滑动窗口的概念。在遍历过程中,不断更新左右边界值。



主要思想如下:

  • 利用 map 记录字符的边界下标。

  • 当遍历到某字符时,若在 map 中已存在,则更新窗口的左边界为该字符的边界下标,从而可计算出包含不同字符的区间长度。



比如 abca。map 中记录 a 的边界下标为 1,那么在遍历到最后一个 a 时,区间长度为 3 - 1 + 1 = 3



注意:左边界更新时的取值应该是当前值与 map 中的值较大的那个。



比如 abba。当遍历到最后一个 a 时, 左边界为 2,而此时 map 中记录的值为 1。若直接取 map 中的值,则会计算错误。



js 代码如下:

var lengthOfLongestSubstring2 = function (s) {
// key 为字符,value 为字符的 index + 1,如果有相同的字符,可根据 value 计算出不重复的区间
let map = new Map()
let longestLen = 0

let i = 0
let j = 0
while (i < s.length) {
if (map.has(s[i])) {
// 取出对应的左边界,取其最大值。因为有可能重复的字符在左边,比如 abba,遍历到最后一个 a,它对应的值是 1,而此时 j = 2, 因此需要取最大值。
j = Math.max(map.get(s[i]), j)
}

const len = i - j + 1
longestLen = Math.max(len, longestLen)

// 设置左边界
map.set(s[i], i + 1)
i += 1
}

return longestLen
}



发布于: 2020 年 07 月 08 日 阅读数: 23
用户头像

liu_liu

关注

不要相信自己的记忆力 2017.11.13 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode 3. Longest Substring Without Repeating Characters