05.最长回文子串.md

动态规划

var longestPalindrome = function(s) {
  if(s.length < 2) return s;
  const len = s.length, dp = new Array(len);
  for(let i = 0; i < len; i ++) {
    dp[i] = new Array(len);
    dp[i][i] = true;
  }
  let max = 1, begin = 0;
  for(let j = 1; j < len; j ++) {
    for(let i = 0; i < j; i ++) {
      if (s.charAt(i) != s.charAt(j)) {
        dp[i][j] = false;
      } else {
        if (j - i < 3) {
          dp[i][j] = true;
        } else {
          dp[i][j] = dp[i+1][j-1]
        }
      }
      if (dp[i][j] && j - i + 1 > max) {
        max = j - i + 1;
        begin = i;
      }
    }
  }
  return s.substr(begin, max)
};

中心扩散法

var longestPalindrome = function(s) {
  if(s.length < 2) return s;
  const len = s.length;
  let res = s.substr(0, 1), maxLen = 1;
  for(let i = 0; i < len - 1; i ++) {
    let oddStr = centerSpread(s, i, i);
    let evenStr = centerSpread(s, i, i + 1);
    let maxStr = oddStr.length > evenStr.length ? oddStr : evenStr;
    if (maxStr.length > maxLen) {
      maxLen = maxStr.length;
      res = maxStr
    }
  }
  return res
};

function centerSpread(s, i, j) {
  const len = s.length;
  let left = i, right = j;
  while(left >= 0 && j < len) {
    if (s[left] == s[right]) {
      left--;
      right++;
    } else {
      break;
    }
  }
  return s.substring(left+1, right)
}