Shortest Palindrome


  • 0
    A

    Click here to see the full article post


  • 0
    J

    #3 Implementation may not be able to handle the case if '#' is in string s.
    Here is an implementation to remove the limitation.

            string rev(s.rbegin(), s.rend());
            if (s == rev)
                return s;
            vector<int> lps(rev.size(), 0);
            int len = 0;
            for (int i = 1; i < rev.size(); i++) {
                while (len > 0 && rev[i] != s[len])
                    len = lps[len - 1];
                if (rev[i] == s[len])
                    len++;
                lps[i] = len;
            }
            return rev + s.substr(len, s.size() - len);
    

  • 0
    A

    @JianMa Thank you for your suggestion. We tried to keep the implementation similar to the original KMP routine for easier understanding. But would surely incorporate the solution as an improvement :)


  • 0
    M

    For Solution #2, why the time cost is O(NlogN) rather than o(N) when the article claims that the size of string is reduced by half each recursion?
    Let T(N) indicates the time complexity of the algorithm in regard of a string of length N. T(N) = T(N/2) +O(N). By replacement, we have T(N) = O(N) + O(N/2) + O(N/4) + ... + O(1) <= O(2N) = O(N). So I think T(N) = O(N) for Solution #2.


  • 0
    A

    @MITCHELLHE Thanks for the rectification. You are right, the time complexity has been calculated incorrectly and will be updated.


  • 0
    C

    For solution #2, the worst timing complexity is O(n^2), although in each iteration the string is divided into 2 part, is possible the s[i:] part has very few letters or even only 1 letter. Thus T(N) = T(N-1) + O(N) --> O(n^2)
    e.g. s = "aababababababababababa"
    @MITCHELLHE @abhinavbansal0


  • 0
    A

    @CONOVER yes you are right. Extremely sorry to have missed this case. Thank you for the correction :)


  • 0
    U

    The algorithm to generate lookup table can be improved. There is no need to assign t = f(i-1) during each iteration. t is simply pointing to the first letter outside the longest prefix. Therefore, the whole idea to do f[i] = ++t is to both assign f[i] with the right value and move t to the right position for next iteration.
    f(0) = 0
    for(i = 1; i < n; i++)
    {
    while(t > 0 && b[i] != b[t])
    t = f(t-1)
    if(b[i] == b[t]){
    f(i) = ++t;
    }

    Should do the work.


  • 0
    S

    For no.1 (brute force), iterating over every character in the string is O(n), but every substring comparison is O(1) in Java. So the total time complexity should be O(n) in Java


  • 0
    M

    Comparing substrings in Java cannot be done in O(1). As a proof, if it could, it would be possible to compare whole strings in O(1) by simply splitting them up after the first character and comparing the substrings you are left with.


  • 0
    C

    I did this in javascript and I keep timing out even though my solution is O(n). I don't think its even possible to do.


  • 0
    M

    tried both the first and the second methods in Python, all time limit error.


  • 0

    @meame2010 said in Shortest Palindrome:

    tried both the first and the second methods in Python, all time limit error.

    I just tried that as well and got both accepted fine.


Log in to reply
 

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