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

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