Leetcode5最长回文子串(中心拓展法和动态规划法)

Leetcode5最长回文子串(中心拓展法和动态规划法)

给你一个字符串s，找到s中最长的回文子串。

答题

/**
 \* @param {string} s
 \* @return {string}
 */
var longestPalindrome = function longestPalindrome(s){
  let n = s.length;
  let res = '';
  let dp = Array.from(new Array(n),() => new Array(n).fill(false));

  for(let i = n-1; i >= 0; i--){
​    for(let j = i; j < n; j++){
​      dp[i][j] = s[i] == s[j] && (j - i < 3 || dp[i+1][j-1]);
     
​      if(dp[i][j] && j - i + 1 > res.length){
​        res = s.substring(i,j+1);
​      }
​    }
  }
  return res;
};

这道题一般有两种做法，一个是上面给出的动态规划解法

还有一个是中心拓展法

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    if(s.length < 2) {
        return s
    }

    let start = 0
    let maxLength = 1
    function expandAroundCenter(left, right) {
        while(left >= 0 && right < s.length && s[left] === s[right]) {
            if(right - left + 1 > maxLength) {
                maxLength = right - left + 1
                start = left
            }
            left--
            right++
        }
    }
    for(let i=0; i<s.length; i++) {
        expandAroundCenter(i - 1, i + 1)
        expandAroundCenter(i, i + 1)
    }
    return s.substring(start, start + maxLength)
};

动态规划方法就是设一个数组“dp[i] [j]“”代表的是字符串从i到j位置的能否构成一个回文子串，其中动态转移方程的边界条件分两种情况，针对一个字符串而言，它总是回文，针对两个字符串而言，需要看这两个相邻的字符串是否相等。而转移方程则是这样判断的；i+1到j、i到j-1、i+1到j-1是否是回文，如果是的话，则dp[i] [j]也是回文。同时更新一下res的长度

中心扩散方法则是以某个字符串为起点，判断以它为中心的字符串是否是回文，或者判断以i和i+1为中心的字符串是否是回文。

前者空间换时间，减少了一些计算，还是值得好好学一下的。