最长回文子串-5

[sl1673495]

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设  s 的最大长度为 1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：

输入: "cbbd"
输出: "bb"

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

动态规划

参考：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zhong-xin-kuo-san-dong-tai-gui-hua-by-liweiwei1419

第 1 步：定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。

第 2 步：思考状态转移方程
在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：

dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]

如果 s[i] 和 s[j] 不相等的话，那说明此时结果一定为 false，如果这两个字符相等，就可以进一步考虑把它们去掉以后中间的子串是否是回文子串了。

如果 dp[i + 1][j - 1] 是 undefined，也说明这个结果为 true，因为只有在 i 和 j 相差为 1 的情况，比如 dp[0][1] 这种情况下，i 会超出 j，也就是起点超出终点，此时从 dp 表里查出的肯定是 undefined，但是这种情况下两头的字符都相等了，那它也一定是回文子串。

在每次循环中都和全局存在的 max变量对比，一旦发现就更新他它，并且更新 begin 起始位置，最后 substr 一次即可得到答案

/**
 * @param {string} s
 * @return {string}
 */
let longestPalindrome = function (s) {
  let n = s.length
  if (n < 2) {
    return s
  }

  let dp = []
  for (let i = 0; i < n; i++) {
    dp[i] = []
    dp[i][i] = true
  }

  let max = 0
  let begin = 0
  for (let j = 1; j < n; j++) {
    for (let i = 0; i < j; i++) {
      if (s[j] !== s[i]) {
        dp[i][j] = false
      } else {
        let indent = dp[i + 1][j - 1]
        if (indent === undefined || indent === true) {
          dp[i][j] = true
        } else {
          dp[i][j] = false
        }
      }

      if (dp[i][j] === true && j - i > max) {
        max = j - i
        begin = i
      }
    }
  }
  return s.substr(begin, max + 1)
}

中心扩散法

中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

• 奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
• 偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

let longestPalindrome = function (s) {
  let n = s.length
  if (n < 2) {
    return s
  }

  let begin = 0
  let max = 1

  let spread = (start, end) => {
    while (s[start] === s[end] && start >= 0 && end < n) {
      let len = end - start + 1
      if (len > max) {
        max = len
        begin = start
      }
      start--
      end++
    }
  }

  for (let mid = 0; mid < n; mid++) {
    spread(mid, mid)
    spread(mid, mid + 1)
  }

  return s.substr(begin, max)
}