方法一：动态规划
- 思路与算法
- js实现
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let len=s.length;
if(len < 2){
return s
}
let maxLen = 1;
let begin = 0;
// dp[i][j]表示s[i...j]是否是回文串
let dp = new Array(len)
for(let i=0;i<len;i++){
dp[i]=new Array(len)
}
// 初始化：所有长度为1对子串都是回文串
for(let i=0;i<len;i++){
dp[i][i]=true
}
console.log(dp)
// 递推开始，先枚举子串长度
for(let L =2;L<=len;L++){
// 枚举左边界，左边界的上限设置可以宽松一些
for(let i=0;i<len;i++){
// 由L和i可以确定右边界，即j-i+1=L得
let j=L+i-1
// 如果右边界越界，就可以退出当前循环
if(j>=len){
break;
}
if(s[i]!==s[j]){
dp[i][j]=false
}else{
if(j-i<3){
// aa或aba格式的
dp[i][j]=true
}else{
dp[i][j]=dp[i+1][j-1]
}
}
// 只要dp[i][j]===true成立，就表示子串s[i...j]是回文，此时记录回文长度和起始位置
if(dp[i][j]&&j-i+1>maxLen){
maxLen=j-i+1
begin = i
console.log(s.substring(begin,begin+maxLen))
}
}
}
return s.substring(begin,begin+maxLen)
};
- 复杂度分析
时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
方法二：中心扩展算法
-
思路与算法
中心扩展算法-思路与算法.png - js实现
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if(s==null||s.length<1){
return ''
}
let start=0,end=0
for(let i=0;i<s.length;i++){
let len1=expandAroundCenter(s,i,i)
let len2=expandAroundCenter(s,i,i+1)
let len = Math.max(len1,len2)
if(len>end-start){
start=i-Math.floor((len-1)/2)
end=i+Math.floor(len/2)
console.log('i----start---end',i,start,end)
}
}
return s.substring(start,end+1)
};
function expandAroundCenter(s,left,right){
while(left>=0&&right<s.length&&s[left]===s[right]){
left--
right++
}
return right-left-1
}
