LeetCode Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

題意就是找最長的回文子串。

以每個點做中心點然後向外擴充的做法：

class Solution {
public:
        string longestPalindrome(string s) {
        string ans;
        int len = 0, low = 0, high = 0;
        for(int i = 0; i < s.size(); i++){
            int j = p1(s, i);
            if((j-i)*2+1 > len){
                low = 2*i - j;
                high = j;
                len = high - low + 1;
            }
            j = p2(s, i);
            if((j-i)*2 > len){
                low = 2*i-j+1;
                high = j;
                len = (j-i)*2;
            }
        }
        for(int i = low; i <= high; i++)
            ans += s[i];
        return ans;
    }
    int p1(const string &s, int cur){
        int i = cur, j = cur;
        while(i >=0 && j < s.size()){
            if(s[i] != s[j])
                break;
            i--;
            j++;
        }
        return j-1;
    }
    int p2(const string &s, int cur){
        int i = cur, j = cur+1;
        while(i >=0 && j < s.size()){
            if(s[i] != s[j])
                break;
            i--;
            j++;
        }
        return j-1;
    }
};
           

動态規劃的做法

class Solution {
    public:
    string longestPalindrome(string s) {
        string ans;
        bool dp[1005][1005] = {false};
        int n = s.length();
        for(int i = 0; i < n; i++)
            dp[i][i] = true;
        for(int i = 0; i < n-1; i++)
            dp[i][i+1] = (s[i] == s[i+1]);
        
        for(int j = 2; j < n; j++){
            for(int i = j-2; i >= 0; i--){
                if((s[i] == s[j]) && (dp[i+1][j-1]))
                    dp[i][j] = true;
            }
        }
        int low = 0, high = 0, len = 0;
        for(int i = 0; i < n; i++)
            for(int j = i; j < n; j++){
                if(dp[i][j] && (j-i+1) > len){
                    low = i;
                    high = j;
                    len = high - low + 1;
                }
            }
        ans = s.substr(low, len);
        return ans;
    }
};
           

雖然時間複雜度都為O(n),但動态規劃比中心擴充的速度要慢一點，因為向外擴充很多情況下擴充一小段就跳出了，動态規劃還一直找下去。

還有一個Manacher algorithm 時間複雜度是O(n),

string longestPalindrome(string str) {
    int len=str.length();
    if(len<=1)return str;
    string str1=str;
    reverse(str1.begin(),str1.end());
    if(str1==str)
        return str;
    string s;
    s += "$#";
    for(int i = 0; i < len; i++){
        s += str[i];
        s += "#";
    }
    s +="$";
    int n=s.size();
    int mx=0,Maxl=0,id=0;
    int *p = new int[n];
    memset(p,0,sizeof(p));
    for(int i=1;i<n-1;i++){
        p[i]=mx>i?min(mx-i,p[2*id-i]):1;
        while(s[i-p[i]]==s[i+p[i]])
            p[i]++;
        if(p[i]>mx-i){
            mx = p[i]+i;
            id=i;
        }
        Maxl=max(Maxl,p[i]);
    }
    int mid=0;
    for(int i=0;i<n;i++){
        if(p[i]==Maxl)
            mid=i;
    }
    int size=Maxl-1;
    delete []p;
    if(mid%2==0)
        return str.substr(mid/2-size/2-1,size);
    else
        return str.substr((mid-size-1)/2,size);
}