【 LeetCode 5】 最长回文子串 (中等) 动态规划
程序员文章站
2022-07-13 23:25:18
...
题目:
这题和求最长回文子串长度差不多,只需要记录下最长回文字串的首尾索引即可
求最长回文子串思路来自 算法笔记P437
代码:
class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(!len) return ""; //空字符串
int dp[1000][1000]={0},l=0,r=0; //l r记录首尾索引
for(int i=0;i<len;i++) //先处理长度为1 和 2的回文
{
dp[i][i]=1; //自身为长度1的回文
if(i<len-1)
{
if(s[i]==s[i+1]) //相邻相等,长度为2
{
dp[i][i+1]=1;
l=i,r=i+1;
}
}
}
for(int i=3;i<=len;i++) //处理长度大于3的回文
{
for(int j=0;j+i-1<len;j++) //首索引
{
int k=j+i-1; //尾索引
if(s[j]==s[k] && dp[j+1][k-1]==1)
{
if(r-l+1 <i) l=j,r=k;
dp[j][k]=1;
}
}
}
string ans; //存答案
for(int i=l;i<=r;i++)
ans+=s[i];
return ans;
}
};
上一篇: JQuery 实现简单的聊天对话框
下一篇: JavaFX实现对话框
推荐阅读