最长回文子串

Leetcode
2019-11-28 01:52

动态规划解法

/**
 * @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);
};
验证码