最长回文子串

动态规划

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() < 2)    return s;
        int start = 0, maxlen = 1, n = s.size();
        vector<vector<int>> dp (n,vector<int>(n));
        for(int i = 0; i < n; ++i)
            dp[i][i] = true;        //对角线均为true,因为一个元素肯定是回文子串
        for(int j = 1; j < n; ++j)
        {
            for(int i = 0; i < j; ++i)
            {
                if(s[i] != s[j])    dp[i][j] = false;
                else
                {
                    if((j-1) - (i+1) + 1 < 2)   dp[i][j] = true;    //如果内部区间长度小于等于1
                    else
                    {
                        if(dp[i+1][j-1])    dp[i][j] = true;        //看内部区间是否是回文
                    }
                }

                if(dp[i][j] && j - i + 1 > maxlen)  
                {
                    start = i;
                    maxlen = j - i + 1;  
                }  
            }
        }

        return s.substr(start,maxlen);
    }
};

作者：zrita
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/c-z-by-zrita-19/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。