Shortest Palindrome with recursive solution issue

Question

Debugging the following problem (a recursive solution) and confused what is the logical meaning of the for loop. If anyone have any insights, appreciated for sharing.

Given a string S, you are allowed to convert it to a palindrome by adding characters in front of it. Find and return the shortest palindrome you can find by performing this transformation.

For example:

Given "aacecaaa", return "aaacecaaa".

Given "abcd", return "dcbabcd".

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;

KMP based solution,

public class Solution {
    public String shortestPalindrome(String s) {
        String p = new StringBuffer(s).reverse().toString();
        char pp[] = p.toCharArray();
        char ss[] = s.toCharArray();
        int m = ss.length;
        if (m == 0) return "";

        // trying to find the greatest overlap of pp[] and ss[]
        // using the buildLPS() method of KMP
        int lps[] = buildLPS(ss);
        int i=0;// points to pp[]
        int len = 0; //points to ss[]

        while(i<m) {
            if (pp[i] == ss[len]) {
                i++;
                len++;
                if (i == m)
                    break;
            } else {
                if (len == 0) {
                    i++;
                } else {
                    len = lps[len-1];
                }
            }
        }
        // after the loop, len is the overlap of the suffix of pp and prefix of ss
        return new String(pp) + s.substring(len, m);

    }

    int [] buildLPS(char ss[]) {
        int m = ss.length;
        int lps[] = new int[m];
        int len = 0;
        int i = 1;
        lps[0] = 0;
        while(i < m) {
            if (ss[i] == ss[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len == 0) {
                    i++;
                } else {
                    len = lps[len-1];
                }

            }
        }

        return lps;
    }
}

thanks in advance, Lin

Answer 1

My original comment was incorrect - as you've pointed out, in addition to using j'to check if s is a complete Palindrome, j is also used to find (intelligently guess?) the index around which to wrap + reverse the trailing characters from the longest palindrome which might exist at the beginning of the string. My understanding of the algorithm is as follows:

e.g. aacecaaa gives j = 7, resulting in

`aacecaaa` is `aacecaa` (palindrome) + `a` (suffix)

so the shortest palindrome appending to the start is:

`a` (suffix) + `aacecaa` + `a` (suffix)

Where the suffix consists of more than one character it must be reversed:

`aacecaaab` is `aacecaa` (palindrome) + `ab` (suffix)

So the solution in this case would be:

`ba` + `aacecaa` + `ab` (suffix)

In the worst case scenario j = 1 (since a will match when i=0 and j=0), e.g. abcd has no palindrome sequence in it, so the best which can be done is to wrap around the first character

dcb + a + bcd

To be honest, I'm not 100% confident that the algorithm you are debugging will work correctly in all cases but can't seem to find an a failed test case. The algorithm is certainly not intuitive.

Edit

I believe the shortest Palindrome can be derived deterministically, without the need for recursion at all - it seems that in the algorithm you are debugging, the recursion masks a side effect in the value of j. In my opinion, here's a way to determine j in a more intuitive manner:

private static String shortestPalindrome(String s) {
    int j = s.length();
    while (!isPalindrome(s.substring(0, j))) {
        j--;
    }
     String suffix = s.substring(j);
    // Similar to OP's original code, excluding the recursion.
    return new StringBuilder(suffix).reverse()
              .append(s.substring(0, j))
              .append(suffix)
              .toString();  
}

I've pasted some test cases with an implementation of isPalindrome on Ideone here