问题

给定一个字符串 S，找出其最长的回文子字符串。S 的最大长度为1000。

举例

输入："babad"

输出："bab"
（注："aba" 也是一个正确的结果）

思路

若长度为 L 的字符串为回文，则去掉首尾的字符，长度为 L-2 的字符串也为回文。
即全局最优解包含局部最优解。

最小子问题

1. 单个字符独立成为一个回文字符串
2. 相邻的两个相同字符，是一个回文字符串

递推方程

设置一个 L*L 的矩阵 D，D[i][j] 的值为 ture 或 false， 表示从 i 起始 j 终止的字符串是否为回文。
则有：

D[i][j] = (D[i] === D[j]) && D[i+1][j-1]
（若第 i 个字符与第 j 个字符相同，且从 i+1 起始 j-1 终止的字符串为回文，则有从 i 起始 j 终止的字符串也为回文）

解法

function handleStr(str) {
  let L = str.length
  let d = []
  for(let i=0;i<L;i++) { // 初始化矩阵D，且先将最小子问题1的情况都设置为true
    let arr = []
    arr[i] = true
    d[i] = arr
  }
  
  let maxLen = 1,
      resIndex = 0
  
  for(let i=0;i<L;i++) { // 再将最小子问题2的情况都设置为true
    if(str[i] === str[i+1]) {
      d[i][i+1] = true
      if(maxLen < 2) { // 如果最小子问题成立，则最长回文字符串为2
        maxLen = 2
        resIndex = i
      }
    }
  }
  
  
  for(let len=3;len<=L;len++) { // 从长度为3开始逐渐增长的检查回文字符串
    for(let i=0;i<L-len+1;i++) { // 从第0个位置开始，依据最小子问题1、2来依次检查回文字符串
      if(str[i] === str[i+len-1] && d[i+1][i+len-2]) {
        d[i][i+len-1] = true
        if(len > maxLen) { // 满足条件时，保存回文字符串长度和起始位置
          maxLen = len
          resIndex = i
        }
      }
    }
  }
  
  return str.substr(resIndex, maxLen)
}