O(n) solution by using Rabin-Karp


  • 0
    class Solution {
        public String shortestPalindrome(String s) {
            int n = s.length();
            int[] hash = new int[n + 1], exp = new int[n + 1];
            exp[0] = 1;
            int mul = 10000007;
            for (int i = n - 1; i >= 0; i--)
                hash[i] = hash[i + 1] * mul + s.charAt(i);
            for (int i = 1; i <= n; i++)
                exp[i] = exp[i - 1] * mul;
            
            int maxLen = 0;
            int hashl = 0;
            for (int i = 0; i < n; i++) {
                hashl = hashl * mul + s.charAt(i);
                int hashr = hash[0] - hash[i + 1] * exp[i + 1];
                if (hashl == hashr) 
                    maxLen = i + 1;
            }
            String rev = new StringBuilder(s).reverse().toString();
            return maxLen == 0 ? "" : rev + s.substring(maxLen);
        }
    }
    

Log in to reply
 

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