My 7-lines recursive Java solution


  • 138

    The idea is to use two anchors j and i to compare the String from beginning and end.
    If j can reach the end, the String itself is Palindrome. Otherwise, we divide the String by j, and get mid = s.substring(0, j) and suffix.

    We reverse suffix as beginning of result and recursively call shortestPalindrome to get result of mid then appedn suffix to get result.

        int j = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(j)) { j += 1; }
        }
        if (j == s.length()) { return s; }
        String suffix = s.substring(j);
        return new StringBuffer(suffix).reverse().toString() + shortestPalindrome(s.substring(0, j)) + suffix;

  • 5
    Q

    This is an elegant solution, can you explain more about why this algorithm will produce the shortest palindrome? And what will be the time complexity? Thanks.


  • 0
    C

    Very clean and good answer.
    Anyone knows how to explain this solution?


  • 0

    I'm not sure the time complexity. I think it's O(nlog(n)) but I don't know how to prove it.


  • 0
    J

    This is O(n) algorithm IMO. In the two extreme cases where s itself is a palindrome and where you have to copy the entire string and reverse it to make a palindrome, it's both O(n). Very good answer. ps: You could use StringBuilder instead of StringBuffer, it reflects a much shorter running time.


  • 0

    I'm not sure it's O(n). How can prove two extreme cases is the worst case?


  • 1
    Q

    Brilliant solution. While not a proof, out of curiosity I decided to count how many recursive calls are needed to pass all tests, and the answer is 2. So function is called 3 times total at most.
    I think the upper bound of complexity is O(N(lg(26))) which is O(N)


  • 0

    I wanna construct a worst case, that may need more than 2 times recursive calls. But I can't find a good model to construct that.

    I mean the tests may not cover all worst cases.


  • 0
    Q
    This post is deleted!

  • 4
    Q

    I did bunch of expriments and worst performance is achieved having just 2 distinct characters in a string randomy distributed. (The ratio of characters doesn't have to be the same) Turns out that worst case performance is 2N. While number of calls is logarithmic, due to size reduction on each call total operations converges to linear value.
    Here are test results of shuffled array of 'a' and 'b' of size 2M

    Length of String: 2000000. Total of all lengths: 2000000
    Length of String: 1000503. Total of all lengths: 3000503
    Length of String: 500559. Total of all lengths: 3501062
    Length of String: 250657. Total of all lengths: 3751719
    Length of String: 125204. Total of all lengths: 3876923
    Length of String: 62644. Total of all lengths: 3939567
    Length of String: 31254. Total of all lengths: 3970821
    Length of String: 15495. Total of all lengths: 3986316
    Length of String: 7691. Total of all lengths: 3994007
    Length of String: 3822. Total of all lengths: 3997829
    Length of String: 1919. Total of all lengths: 3999748
    Length of String: 961. Total of all lengths: 4000709
    Length of String: 496. Total of all lengths: 4001205
    Length of String: 240. Total of all lengths: 4001445
    Length of String: 114. Total of all lengths: 4001559
    Length of String: 64. Total of all lengths: 4001623
    Length of String: 36. Total of all lengths: 4001659
    Length of String: 24. Total of all lengths: 4001683
    Length of String: 15. Total of all lengths: 4001698
    Length of String: 8. Total of all lengths: 4001706
    Length of String: 5. Total of all lengths: 4001711
    Length of String: 2. Total of all lengths: 4001713
    

  • 47
    L

    Hi I try to explain the elegant solution of @xcv58. At first I clarify some notation: in the following paragraph mid point of a palindrome "abcdcba" denotes 'd'; when I say charAt(1)=='b' pairs with charAt(5)=='b', I mean they are at symmetric positions.

    Take "gxybakbkabbfmbnnnjjjyxqg" as example. After for loop j stops at j'==10 where charAt(10)=='b'. Then it reaches such a status: To make the final result be a valid palindrome, in the final result this 'b' at index j' neither could be the mid point nor could pair with any other 'b' in the string s.

    Now we prove this by contradiction, in 1st case if charAt(j') is the mid point, then substring(0,2*j'+1) should be palindrome (otherwise the final result was not palindrome), and when substring(0,2*j'+1) is palindrome, using our for loop mentioned before, j would stops with index at least 2*j'+1, which is a contradiction. Similarly in 2nd case if charAt(j') could pair with some charAt(i) in the final result, then substring(0,j'+i+1) should be palindrome, if j'+i+1 is already > s.length(), it's a contradiction(we can't add characters at backside); else when substring(0,j'+i+1) is palindrome, j would stops with index at least j'+i+1, which is a contradiction.

    Then we have the conclusion: to pair the charAt(j)=='b' in the final result, we must add new char 'b' from the front of s, and since they are paired, all chars on the right side of j should be paired by some newly added chars => We MUST add substring(j)'s reverse string in front of s => This is the shortest way to transform s to palindrome. Later we deal with substring(0,j) recursively.


  • 0

    Cool, I'm too lazy to do this.

    But still we don't have a formal proof for time complexity.


  • 0
    L

    Hi @qianzhige, for the reason it's shortest palindrome, you could see my explanation below :)


  • 0
    L

    Thanks for your comment. Maybe later we would try to find a proof for time complexity. Now it's 2am and I'm too sleepy :)


  • 0

    Of course, take it easy.


  • 0
    This post is deleted!

  • 0
    L

    Hi, I think I can't prove the linear time complexity. Since I construct a test case that "abacfghcabakmnchgfcabaiuytrcfghcnmkabachgfcaba" in which we need to call the function for 5 times.


  • 0
    L

    "abacfghcabakmnchgfcabaiuytrcfghcnmkabachgfcaba" This is a test case which need 5 calls...


  • 0
    D

    Brilliant code and brilliant test case. I agree that the algorithm is O(nlogn).


  • -1
    This post is deleted!

Log in to reply
 

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