最长回文子串（LeetCode 5）

给你一个字符串 s，找到 s 中最长的回文子串。 注：回文字符串就是正反都一样的字符串，例如 ‘abba’

示例1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例2：

输入：s = "cbbd"
输出："bb"

示例3：

输入：s = "a"
输出："a"

示例4：

输入：s = "ac"
输出："a"

思路分析：
此题是动态规划的经典题目：
首先我们要确定状态转移方程：

1. 如果一个字符串是回文字符串，那儿它左右两边加上一个相同的字符串它还是回文字符串
2. 如果一个回文字符串左右两边加上不同的字符，得到的就不是回文字符串了

我们用dp[i][j]表示字符串s从i到j（闭区间）是否是回文字符串，得到状态转移方程

if(s[i] === s[j] && dp[i+1][j-1]){
    dp[i][j] = true
}

由于dp[i][j]的计算依赖dp[i+1][j-1]，所以外层i遍历的时候是从后往前
题解：

var longestPalindrome = function(s) {
  // babad
  // tag : dp
  if (!s || s.length === 0) return "";
  let res = s[0];

  const 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) {
        // specail case 1
        dp[i][j] = true;
      }else if (j - i === 1 && s[i] === s[j]){
        // specail case 2
        dp[i][j] = true;
      }else if (s[i] === s[j] && dp[i + 1][j - 1]) { 
        // state transition
        dp[i][j] = true;
      }

      if (dp[i][j] && j - i + 1 > res.length) {
        // update res
        res = s.slice(i, j + 1);
      }
    }
  }
  return res;
};