动态规划解法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} str
 * @return {string}
 */
var longestPalindrome = function(str) {
  const s = str.split('');
  const p = Array.from(new Array(s.length), x => new Array(s.length));
  
  for (let i = 0; i < s.length; i++) {
    p[i][i] = true;
    if (i + 1 < s.length) {
      p[i][i+1] = s[i] === s[i+1];
    }
  }
  for (let j = 2; j < s.length; j++) {
    for (let i = 0; i < s.length - 2; i++) {
      if (i + j < s.length) {
        p[i][i+j] = p[i+1][i+j-1] && s[i] === s[i+j]
      }
    }
  }
  let m = 0, n = 0
  for (let i = 0; i < s.length ; i++) {
    for (let j = i; j < s.length; j++) {
      if(p[i][j] && j - i > n - m) {
        m = i;
        n = j;
      }
    }
  }
  return str.slice(m, n+1);
};