最长回文子串.md

最长回文子串

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

示例 1：

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

示例 2：

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

动态规划

/**
 * 最长回文子串
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  if (s.length < 2) return s
  // dp[i]，以第i个字母结尾的所有回文字符串集合
  const dp = Array(s.length).fill(1).map(item => [])
  dp[0] = [s[0]]
  for (let i = 1; i < s.length; i++) {
    // 单个字母是回文
    dp[i].push(s[i])
    // 两个相同的字母也是回文
    if (s[i - 1] === s[i]) {
      dp[i].push(`${s[i]}${s[i]}`)
    }
    dp[i - 1].forEach(item => {
      const lastLen = item.length
      // aba是一个回文，那么xabax也是一个回文
      if (s[i - lastLen - 1] === s[i]) {
        dp[i].push(`${s[i]}${item}${s[i]}`)
      }
    })
  }
  const getListMax = list => list.reduce((pre, cur) => {
    return pre.length > cur.length ? pre : cur
  }, '')
  // 求出最长的回文
  return getListMax(dp.map(item => getListMax(item)))
};

动态规划2

/**
 * 最长回文子串
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
  if (s.length < 2) return s
  // dp[i][j]，从第i个到第j个字符是不是回文
  const dp = Array(s.length).fill(1).map(() => [])
  // 默认第一个字符为最长回文
  let res = s[0]
  // 倒序遍历是为了能够通过i利用到i+1的计算结果
  for (let i = s.length - 1; i > -1; i--) {
    dp[i][i] = true
    for (let j = i + 1; j < s.length; j++) {
      // 左右两个相等也是回文
      if (i + 1 === j && s[j] === s[i]) {
        dp[i][j] = true
      } else if (dp[i+1][j-1] && s[i] === s[j]) {
        // aba能够推出xabax也是回文
        dp[i][j] = true
      }
      if (dp[i][j] && s.substring(i, j+1).length > res.length) {
        res = s.substring(i, j+1)
      }
    }
  }
  return res
};