1.题目链接
5. 最长回文子串 - 力扣(LeetCode)https://leetcode.cn/problems/longest-palindromic-substring/description/
2.题目解析
对于这道题目我们可以使用动态规划的思路来求解,具体思路是,对于一个长度大于2的子串,如果它是回文串的话,那么将它首尾的两个字母去除之后,它仍然是个回文串。例如对于“ababa”,将首尾字符串去掉,剩下的还是回文串,那么我们就可以列出下面状态转移方程:
当子串长度大于2时
当子串长度等于2时
3.代码如下:
class Solution {
public:string longestPalindrome(string s) {int n=s.size();bool f[n][n];memset(f,false,sizeof f);int maxi=0;string res;for(int l=1;l<=n;l++){for(int i=0;i+l-1<n;i++){int j=i+l-1;if(s[i]==s[j]){if(j-i<3){f[i][j]=true;}else if(f[i+1][j-1])f[i][j]=true;if(f[i][j]&&l>=maxi){maxi=l;res=s.substr(i,l);}}}}return res;}
};