KMP Java solution ,but cannot pass the largest test case. Any suggestion?


  • 0
    Z

    The idea is to concat s and reverse s. Then compute the longest prefix which is also suffix.

    public class Solution {
        public String shortestPalindrome(String s) {
            int len = computeLPS(s+reverse(s));
            if(len >= s.length()) return s;
            return reverse(s.substring(len))+s;
        }
        
        //longest proper prefix which is also suffix
        public int computeLPS(String s){
            int[] lps = new int[s.length()]; // lps[0] is  0
            int len = 0;// lenght of the previous longest prefix suffix
            int i=1;
            while(i<s.length()){
                if(s.charAt(i) == s.charAt(len)){
                    len++;
                    lps[i] = len;
                    i++;
                }else {
                    if(len != 0){
                        len = lps[len-1];
                    }else {
                        lps[i] = 0;
                        i++;
                    }
                }
            }
            return len;
        }
        public String reverse(String s){
            String res="";
            for(int i=s.length()-1;i>=0;i--){
                res+=s.charAt(i);
            }
            return res;
        }
    }
    

    [1]: http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/


  • 0
    L

    Maybe it's because what you use is MP algorithm, KMP is an improvement based on it and is faster. You could try KMP.


Log in to reply
 

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