题解 | 最长回文子串

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    bool IsValid(string str){
        if(str.empty()||str.size()==1) return true;
        
        int n= str.size();
        int len = n/2;
        for(int i=0;i<len;i++){
            if(str.at(i)!=str.at(n-i-1)) return false;
        }
        return true;
    }
    int getLongestPalindrome(string A) {
        // write code here
        if(A.empty()) return 0;
        if(A.size()==1) return 1;
        int n=A.size();
        int max_len=1;

        vector<vector<bool >> dp(n,vector<bool >(n,false));
        for(int i=1;i<n;i++) dp[i][i]=true;
        for(int i=1;i<n;i++)for(int j=i-1;j>=0;j--){
            if(A.at(i)!=A.at(j)) dp[i][i]=false;
            else {
                if(i-j-1<=1) dp[i][j]=true;
                else dp[i][j]=dp[i-1][j+1];   
                if(dp[i][j]==true) max_len = max(max_len,i-j+1);
            }
        }
        return max_len;
    }
};

// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 
//      * @param A string字符串 
//      * @return int整型
//      */
//     bool IsValid(string str){
//         if(str.empty()||str.size()==1) return true;
        
//         int n= str.size();
//         int len = n/2;
//         for(int i=0;i<len;i++){
//             if(str.at(i)!=str.at(n-i-1)) return false;
//         }
//         return true;
//     }
//     int getLongestPalindrome(string A) {
//         // write code here
//         if(A.empty()) return 0;
//         if(A.size()==1) return 1;
//         int n=A.size();
//         int res=1;
//         int tmp_len = 0;
//         vector<int > dp(n,1);
//         for(int i=1;i<n;i++){
//             tmp_len = 0;
//             for(int j=0;j<i;j++){
//                 string tmp_str = A.substr(j,i-j+1);
//                 if(IsValid(tmp_str)) {tmp_len = max(tmp_len,i-j+1);res = max(res,tmp_len);}
//             }
//         }
//         return res;
//     }
// };