LeetCode之最长回文子串

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;}
};