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