LeetCode 3. Longest Substring Wi

2020-07-08  本文已影响0人  微微笑的蜗牛

问题描述

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

栗 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

条件也很简单,如下:

栗子详解

举个栗子,假设字符串为 pwwekew

当遍历到某个字符时,很显然,以该字符开始,到该字符为止的子串长度都为 1。

处理过程如下:

所以最终的结果为,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
};

更优解法

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

主要思想如下:

比如 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
}
上一篇 下一篇

猜你喜欢

热点阅读