关于javascript: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 为核心的字符串是否是回文。

前者空间换工夫，缩小了一些计算，还是值得好好学一下的。