题解 | #密码截取#

最长回文子串，参考一下链接

Leetcode算法5.最长回文子串

方法：动态规划

时间复杂度O(n^2) 空间复杂度O(n^2)

#include<iostream>
#include<string>
#include<vector>

using namespace std;

void func(string &input){
    int n = input.size();
    if(n < 2){
        cout<<n<<endl;
        return;
    }
    
    vector<vector<bool>> dp(n, vector<bool>(n, false));
    for(int i = 0; i < n; i++)dp[i][i] = true;
    
    int maxLen = 1;
    //int begin = 0;

    for(int L = 2; L <= n; L++){
        for(int i = 0; i < n; i++){
            int j = L + i - 1;
            if(j >= n)break;
            
            if(input[i] == input[j]){
                if(j-i < 3){
                    dp[i][j] = true;
                }
                else
                    dp[i][j] = dp[i+1][j-1];
            }
            
            if(dp[i][j] && j-i+1 > maxLen){
                maxLen = j-i+1;
                //begin = i;
            }
            
        }
    }
    cout<<maxLen<<endl;
}

int main(){
    string input;
    while(cin>>input){
        func(input);
    }
    return 0;
    
}