Leetcode刷题

1. 最长回文子串

动态规划解法：

class Solution {
public:
    string longestPalindrome(string s) {
        int length = s.size();
        vector<vector<int>> dp(length, vector<int>(length));
        string ans;
        int max=1;
        // dp[i][j] = (dp[i]==dp[j]) && (dp[i+1][j-1] || j-i<3)
        for(int j=0; j<length; j++){
            for(int i=0; i<j+1; i++){
                if(s[i] != s[j]) dp[i][j]=false;
                else if(j-i<3) dp[i][j]=true;
                else if(dp[i+1][j-1]) dp[i][j]=true;
                int l = j-i+1;
                if(dp[i][j] && l>ans.size()) ans = s.substr(i,l);
            }
        }
        return ans;

    }
};

中心扩散法：

class Solution {
public:
    pair<int, int> expandAroundCenter(const string& s, int left, int right){
        while(left>=0 && right<s.size() && s[left]==s[right]){
            --left;
            ++right;
        }
        return {left+1, right-1};
    }

    string longestPalindrome(string s) {
        int start=0, end=0;
        for(int i=0; i<s.size();++i){
            auto [left1, right1] = expandAroundCenter(s, i, i);
            auto [left2, right2] = expandAroundCenter(s, i, i+1);
            if(right1-left1>end-start){
                start=left1;
                end = right1;
            }
            if(right2-left2>end-start){
                start = left2;
                end = right2;
            }
        }
        return s.substr(start, end-start+1);


    }
};

Leetcode刷题

原文：https://www.cnblogs.com/JetBlock/p/12941932.html