214. Shortest Palindrome

/**
 * KMP(Knuth–Morris–Pratt) String-Search Algorithm (Only create the lookup
 * table)
 *
 * We add "#" here to force the match in reverse(s) starts from its first index.
 * What we do in KMP here is trying to find a match between prefix in s and a
 * postfix in reverse(s). The match part will be palindrome substring.
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input string
 */
class Solution1 {
    public String shortestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }
        String reverseStr = new StringBuilder(s).reverse().toString();
        String tempStr = s + "#" + reverseStr;

        int[] table = getKmpLookupTable(tempStr);

        String strToBeAdded = new StringBuilder(s.substring(table[table.length - 1])).reverse().toString();

        return strToBeAdded + s;
    }

    private int[] getKmpLookupTable(String s) {
        int[] lookupTable = new int[s.length()];
        int index = 0;
        int i = 1;
        while (i < s.length()) {
            if (s.charAt(i) == s.charAt(index)) {
                lookupTable[i] = index + 1;
                index++;
                i++;
            } else {
                if (index > 0) {
                    index = lookupTable[index - 1];
                } else {
                    i++;
                }
            }
        }
        return lookupTable;
    }
}

/*
 * Two-Pointers and Recursion
 *
 * Time Complexity: O(n^2) Space Complexity: O(n)
 */
class Solution2 {
    public String shortestPalindrome(String s) {
        if (s == null) {
            return "";
        }
        if (s.length() < 2) {
            return s;
        }

        int j = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
        }
        if (j == s.length()) {
            return s;
        }

        String suffix = s.substring(j);
        String suffixRev = new StringBuilder(suffix).reverse().toString();

        return suffixRev + shortestPalindrome(s.substring(0, j)) + suffix;
    }
}