4ms Short Java KMP based Solution with Explanation, no need to extend the string


  • 1
    C

    Build a KMP Partial match table of the string and match it with its reverse. When reaching the end, the unmatched suffix is the part that should be added to the left of the string.

    public class Solution {
        public String shortestPalindrome(String s) {
            if (s.length() <= 1)
                return s;
            char[] c_str = s.toCharArray();
            // the next array stores the failure function of each position.
            int[] next = new int[c_str.length];
            next[0] = -1;
            int i = -1, j = 0;
            while (j < c_str.length-1) {
                if (i == -1 || c_str[i] == c_str[j]) {
                    i ++;
                    j ++;
                    next[j] = i;
                    if (c_str[j] == c_str[i])
                        next[j] = next[i];
                } else i = next[i];
            }
            // match the string with its reverse.
            i = c_str.length - 1; j = 0;
            while (i >= 0 && j < c_str.length) {
                if (j == -1 || c_str[i] == c_str[j]) {
                    i --;
                    j ++;
                } else {
                    j = next[j];
                }
            }
            StringBuilder sb = new StringBuilder();
            for (i = c_str.length-1; i >= j; i --) sb.append(c_str[i]);
            for (char c : c_str) sb.append(c);
            return sb.toString();
        }
    }
    

  • -2

  • 0
    N

    this two lines should be commented out, otherwise it is not longest prefix KMP
    if (c_str[j] == c_str[i])
    next[j] = next[i];


Log in to reply
 

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