写点什么

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 日阅读数: 51
用户头像

liu_liu

关注

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

还未添加个人简介

评论

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