問題

給定一個字符串 S，找出其最長的回文子字符串。S 的最大長度為1000。

舉例

輸入："babad"

輸出："bab"
（注："aba" 也是一個正確的結果）

思路

若長度為 L 的字符串為回文，則去掉首尾的字符，長度為 L-2 的字符串也為回文。
即全局最優(yōu)解包含局部最優(yōu)解。

最小子問題

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個位置開始，依據(jù)最小子問題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)
}