C++ 6ms solution, using KMP algorithm


  • 0
    class Solution {
    public:
    string shortestPalindrome(string s) {
        if (s.size()<=1) return s;
        string srv=s;
        reverse(srv.begin(),srv.end());
        if (srv==s) return s;
        vector<int> next(srv.size(),0);
        int i=1,j=0;
        while(i<srv.size()){
            if (srv[i]==s[j]){
                next[i]=j+1;
                i++;j++;
            }else if (j>0){
                j=next[j-1];
            }else{
                next[i]=0;i++;
            }
        }
        int k=next.back();
        string res="";
        for (int i=s.size()-1;i>=k;i--){
            res+=s[i];
        }
        res+=s;
        return res;
    }
    };

  • 0
    O

    There's a problem with most of the KMP based solutions. Try input "aacecaaazz". Output should be "zzaacecaaazz"
    Leetcode OJ probably doesn't check these cases.


  • 0

    Yes, you are right. There is a bug in the code. Thanks for pointing it out. Good news is I no longer use KMP for this problem. The following straightforward code is much easier to explain in an interview.

    string shortestPalindrome(string s) {
        if (s.size()<=1) return s;
        int sz =s.size();
        int maxSize = 0;
        for (int i=sz/2;i>=0;){
            int j=i;
            while (i<sz-1 && s[i]==s[i+1]) i++;
            while (j>0 && s[j]==s[j-1]) j--;
            int k=0;
            while (j-k>=0 && i+k<sz && s[i+k]==s[j-k]) k++;
            if (j-k==-1) {
                maxSize = i+k;
                break;
            }
            i=j-1;
        }
        string s2 = s.substr(maxSize);
        reverse(s2.begin(),s2.end());
        return s2+s;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.