题解 | #最长回文子串#

1.dp

class Solution {
public:
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    int getLongestPalindrome(string str) {
        // write code here
        if(str.empty()) {
            return 0;
        }
        int n = str.size(),res=0;
        vector<vector<int>> dp(n,vector<int>(n,0));
        for(int len=0;len<n;len++) {
            for(int i=0;i<n-len;i++) {
                int j = i + len;
                if(j==i) {
                    dp[i][j] = 1;
                    res = max(res,dp[i][j]);
                    continue;
                }
                if(j==i+1 && str[i]==str[j]) {
                    dp[i][j] = 2;
                    res = max(res,dp[i][j]);
                    continue;
                }
                if(dp[i+1][j-1]>0 && str[i]==str[j]) {
                    dp[i][j] = dp[i+1][j-1] + 2;
                    res = max(res,dp[i][j]);
                }
            }
        }
        return res;
    }
};