Java KMP accepted, simple idea


  • 2
    T

    the idea is very straight-forward, basically you get p= s.reverse(), and use p as a "long string" and s as a "query pattern" and cast it as a KMP pattern search problem. the only tweak is that we are only search for a ***prefix of **** s, so the only change from standard KMP is to exit on i==length(s), not j==length(pattern)

    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;
        }
    }

  • 0
    L

    Hi @ teddyyyy , nice idea! One little improvement :

    if (i == m)
        break;
    

    This is redundant code, just remove it. :)


Log in to reply
 

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