467. 环绕字符串中唯一的子字符串

解题过程

INFO

题目链接把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串，所以 s 看起来是这样的： "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." 。现在给定另一个字符串 p 。返回 s 中不同的 p 的非空子串的数量

javascript

/**
 * @link https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
 * @title 467. 环绕字符串中唯一的子字符串
 * @description 把字符串 s 看作 "abcdefghijklmnopqrstuvwxyz" 的无限环绕字符串，所以 s 看起来是这样的：
 * "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." 。
 * 现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量
 * @param {string} p
 * @return {number}
 */
// 解法一
// 思路：穷举法，结果测试用例只通过22/82，所以思路还是有问题的，应该是没考虑周全，因为这个方法也比较笨重，果断放弃了
var findSubstringInWraproundString = function (p) {
  const pMap = new Map()
  let total = 1
  let acc = 1
  pMap.set(p[0], 1)

  for (let i = 1; i < p.length; i++) {
    // 注意 25 是字符 a 跟 z 的 Unicode 码点的差值
    if (p[i - 1].charCodeAt() + 1 === p[i].charCodeAt() || p[i - 1].charCodeAt() - 25 === p[i].charCodeAt()) {
      // 前后字符是环绕连续的
      acc++

      if (!pMap.has(p[i])) {
        // 不存在该字符，直接数量加一，算作一个子串数量
        total++
        pMap.set(p[i], 1)
      }

      // 默认连续子字符串加一
      if (!pMap.has(p.slice(i - acc + 1, i + 1))) {
        // 不能重复添加相同的连续环绕字符串
        total++
        pMap.set(p.slice(i - acc + 1, i + 1), 1)
      }
    } else {
      if (acc >= 3) {
        // 判断当前连续的环绕字符是否超过2个
        for (let j = acc - 1; j >= 2; j--) {
          let count = j
          while (count >= 2) {
            total++
            count--
          }
        }
      }

      // 重置累积连续环绕字符串数量
      acc = 1

      // 前后字符不是连续环绕的
      if (!pMap.has(p[i])) {
        // 不存在该字符，直接数量加一，算作一个子串数量
        total++
        pMap.set(p[i], 1)
      }
    }
  }

  // 防止最后都是连续的环绕字符
  if (acc >= 3) {
    // 判断当前连续的环绕字符是否超过2个
    for (let j = acc - 1; j >= 2; j--) {
      let count = j
      while (count >= 2) {
        total++
        count--
      }
    }
  }

  return total
}

// 解法二
// 思路：针对解法一优化思路
// 缺点：执行结果超出时间限制，说明该思路方法还是不够好，放弃优化了
var findSubstringInWraproundString = function (p) {
  const res = [p[0]]
  let acc = 1

  for (let i = 1; i < p.length; i++) {
    res.push(p[i])
    if (p[i - 1].charCodeAt() + 1 === p[i].charCodeAt() || p[i - 1].charCodeAt() - 25 === p[i].charCodeAt()) {
      // 前后连续环绕字符累加
      acc++
    } else {
      if (acc >= 2) {
        // 判断当前连续的环绕字符是否超过2个（字符倒序添加对应的连续字符串）
        let pre = acc
        for (let j = i; j >= i - acc; j--) {
          let count = 1
          const cur = pre

          while (count < cur) {
            res.push(p.slice(j - count - 1, j))
            count++
          }

          pre--
        }
      }

      // 重置累积连续环绕字符串数量
      acc = 1
    }
  }

  // 最后判断，防止遍历最后都是连续环绕的子字符串没有提取
  if (acc >= 2) {
    let pre = acc
    // 判断当前连续的环绕字符是否超过2个（倒序添加）
    for (let j = p.length - 1; j >= p.length - 1 - acc; j--) {
      let count = 1
      const cur = pre

      while (count < cur) {
        res.push(p.slice(j - count, j + 1))
        count++
      }

      pre--
    }
  }

  // 去重处理
  return Array.from(new Set([...res])).length
}

// 解法三
// 思路：看了复雪明烛的题解，原题是Python做的，理解后做出来的，核心思想是子串相关的动态规划，一般状态的定义都是「以位置 ii 作为结尾的、符合要求的子串长度」
// 第一步：存储26个字符的数组，为统计每个字符出现子串长度值，默认第一项的统计字符结尾子串长度为1
// 第二步：遍历字符串统计前后连续子串长度值，只保留最大的子串长度值即可，因为会重复统计子串相同值所以只保留最大值即可
// 第三步：对统计数组子串长度值求和即可
var findSubstringInWraproundString = function (p) {
  const res = new Array(26).fill(0)
  const start = 'a'.charCodeAt()
  let acc = 1 // 连续出现子串的数量
  res[p[0].charCodeAt() - start] = 1

  for (let i = 1; i < p.length; i++) {
    if (p[i - 1].charCodeAt() + 1 === p[i].charCodeAt() || p[i - 1].charCodeAt() - 25 === p[i].charCodeAt()) {
      // 前后连续环绕字符累加
      acc++
    } else {
      // 重置连续子串累加值
      acc = 1
    }

    res[p[i].charCodeAt() - start] = Math.max(acc, res[p[i].charCodeAt() - start])
  }

  // 统计所有字符数量累加
  return res.reduce((pre, cur) => pre + cur)
}

// const result = findSubstringInWraproundString('a') // 1
// const result = findSubstringInWraproundString('cac') // 2
// const result = findSubstringInWraproundString('zab') // 6
// const result = findSubstringInWraproundString('abcd') // 10
// const result = findSubstringInWraproundString('abaab') // 3
const result = findSubstringInWraproundString('zaba') // 6
console.log(result)

解题感受

这一题不好做，解法一和解法二都是想通过暴力破解来做，结果发现是不行的，太多需要考虑的判断情况了。看了几个题解，复雪明烛题解写的最好，通俗易懂，虽然是 Python 写的，翻译成 JavaScript 也很好写，因为跟解法一二有相似支持，只不过他用了数组统计方式是最好的复雪明烛说：遇到子串，一般会想到「滑动窗口」和「动态规划」。确实这两个我都还没抽时间去针对性学一下，后续会加强学习

467. 环绕字符串中唯一的子字符串 ​

解题过程 ​

解题感受 ​

优质题解 ​

467. 环绕字符串中唯一的子字符串

解题过程

解题感受

优质题解