Problem:5. 最长回文子串

思路：暴力枚举最长子串的长度

Accode

class Solution {
public:
    string longestPalindrome(string s) {
        string ans;
        int len = s.length();
        for(int i=1;i<=len;i++){
            for(int j=0;j<len;j++){
                if(j+i-1<len){
                    bool flag = true;
                    for(int l=j,r=j+i-1;l<=r;l++,r--){
                        if(s[l]!=s[r]){
                            flag = false;
                            break;
                        }
                    }
                    if(flag) {
                        if(i>ans.length()) {
                            ans = s.substr(j,i);
                        }
                    }
                }
            }
        }
        return ans;
    }
};

时间复杂度$o(n^3)$

改进：从回文子串的中心开始往左右两边拓展，中心分为长度1,2两种情况，所以两个$o（n^2）$

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.length();
        string ans;
        for(int i=0;i<len;i++){
            int j;
            for(j=0;j<=len;j++){
                if(i-j<0||i+j>=len) break;
                if(s[i-j]!=s[i+j]) break;
            }
            if(ans.length()<2*(j-1)+1){
                ans = s.substr(i-j+1,2*(j-1)+1);
            }
        }
        for(int i=0;i<len;i++){
            int l =i,r = i+1;
            if(s[l]!=s[r]) continue;
            int j;
            for(j=1;j<len;j++){
                if(l-j<0||r+j>=len) break;
                if(s[l-j]!=s[r+j]){
                    break;
                }
            }
            if(ans.length()<2*j){
                ans = s.substr(l-j+1,j*2);
            }
        }
        return ans;
    }
};

时间复杂度：$o(n^2)$