最长回文子串

class Solution {
public:
    string longestPalindrome(string s) {
        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
        for(int i=0;i<s.size();i++){
            dp[i][i]=true;
            if(i>0) dp[i][i-1]=true;
        }
        vector<int> result(2, 0);
        for(int j=1;j<s.size();j++){
            for(int i=j-1;i>=0;i--){
                if(s[j]==s[i]&&dp[i+1][j-1]==true){
                    dp[i][j]=true;
                    if(j-i>=result[1]-result[0]){
                        result[1]=j;
                        result[0]=i;
                    }
                } 
            }
        }
        return s.substr(result[0], result[1]-result[0]+1);
    }
};


class Solution {
public:
    int left = 0;
    int maxLength = 0;
    string longestPalindrome(string s) {
        int result = 0;
        for (int i = 0; i < s.size(); i++) {
            extend(s, i, i, s.size()); // 以i为中心
            extend(s, i, i + 1, s.size()); // 以i和i+1为中心
        }
        return s.substr(left, maxLength);
    }
    void extend(const string& s, int i, int j, int n) {
        while (i >= 0 && j < n && s[i] == s[j]) {
            if (j - i + 1 > maxLength) {
                left = i;
                maxLength = j - i + 1;
            }
            i--;
            j++;
        }
    }
};