Leetcode5最长回文子串(中心拓展法和动态规划法)
原创Leetcode5最长回文子串(中心拓展法和动态规划法)
原创
伯约同学
发布于 2022-03-28 23:01:51
发布于 2022-03-28 23:01:51
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为中心的字符串是否是回文。
前者空间换时间，减少了一些计算，还是值得好好学一下的。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读