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动态规划方法就是设一个数组“dp[i] [j]“”代表的是字符串从i到j位置的能否构成一个回文子串，其中动态转移方程的边界条件分两种情况，针对一个字符串而言，它总是回文，针对两个字符串而言，需要看这两个相邻的字符串是否相等。而转移方程则是这样判断的；i+1到j、i到j-1、i+1到j-1是否是回文，如果是的话，则dp[i] [j]也是回文。同时更新一下res的长度
中心扩散方法则是以某个字符串为起点，判断以它为中心的字符串是否是回文，或者判断以i和i+1为中心的字符串是否是回文。
【Leetcode5最长回文子串(中心拓展法和动态规划法)】前者空间换时间，减少了一些计算，还是值得好好学一下的。
推荐阅读
- JavaScript 引擎是如何实现 async/await 的
- 几种快速排序方法
- ES6新特性拾遗
- JavaScript的继承
- 原型与原型链的个人理解
- uniapp|uniapp 实现保持登录状态
- js|Vue快速入门-个人笔记
- vuex|vuex5 Pinia状态管理
- 青龙教程资源分享|傻妞js插件教程