【LeetCode精选TOP面试题】5-最大回文串

给你一个字符串 s，找到 s 中最长的回文子串。

动态规划解法

解法原出处

思路

用 dp[i][j] 表示从 i-j 是否能形成回文串。

倒着遍历可以简化操作， 这么做的原因是 dp[i][..] 依赖于 dp[i + 1][..]。

对 dp[i][j] 的值有三种情况可以为 true：

• j - i === 0 当前位可作为一个单字符的回文串。
• j - i === 1 && s[i] === s[j] 相邻的两个数相同时可作为一个双字符的回文串。
• s[i] === s[j] && dp[i+1][j-1] 更远位数时两端字符相同且两端向内一位的字符串是一个回文串 dp[i+1][j-1]。

代码

var longestPalindrome = function (s) {
  if (!s || s.length === 0) return "";
  let res = s[0];
  let dp = [];
  // 倒着遍历简化操作， 这么做的原因是dp[i][..]依赖于dp[i + 1][..]
  for (let i = s.length - 1; i >= 0; i--) {
    dp[i] = [];
    for (let j = i; j < s.length; j++) {
      if (j - i === 0) {
        // 同位
        dp[i][j] = true;
      } else if (j - i === 1 && s[i] === s[j]) {
        // 前后两位
        dp[i][j] = true;
      } else if (s[i] === s[j] && dp[i + 1][j - 1]) {
        // 更远位
        dp[i][j] = true;
      }
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.slice(i, j + 1);
      }
    }
  }

  return res;
};
let result = longestPalindrome("babad");
console.log(result);