Two methods in Java, traditional and Manacher, beat 99.77% and 99.12% res.


  • 0
    /**
         * 
         * Technically, Manacher O(n) should beat traditional method O(n^2)
         * 
         * But, because of the limitation of test cases, they perform identically the same.
         * Also, O(c1*n) O(c2 * n^2) c1 is larger than c2 apparently out of Manacher's doing more checks in one move.
         * 
         * It is hard to explain Manacher with several lines.
         * I strongly recommend a video for you. Please watch it at least three time before telling yourself you cannot understand it.
         * 
         * here is the link: [https://www.youtube.com/watch?v=V-sEwsca1ak&t=332s](https://www.youtube.com/watch?v=V-sEwsca1ak&t=332s)
         * 
         */
    public class Solution {
        public String longestPalindromeTradition(String s) {
            char[] arr = s.toCharArray();
            int l = 0;
            int r = 0;
            int left = 0;
            int right = 0;
            int len = arr.length;
            int upper = len;
            while (right < upper) {
                while (right + 1 < len && arr[right + 1] == arr[right]) {
                    right ++;
                }
                int copy = right;
                while (left - 1 >= 0 && right + 1 < len && arr[left - 1] == arr[right + 1]) {
                    left --;
                    right ++;
                }
                if (right - left > r - l) {
                    r = right;
                    l = left;
                    upper = len - ((right - left) >> 1);
                }
                left = ++copy;
                right = left;
            }
            return s.substring(l, r + 1);
            
        }
        
        
        public String longestPalindromeManacher(String s) {
            int l = 0;
            int r = 0;
            int len = (s.length() << 1) + 1 ;
            char[] arr = new char[len];
            arr[0] = '^';
            char[] temp = s.toCharArray();
            int j = 0;
            for (int i = 1; i < arr.length; ++ i) {
                arr[i] = temp[j ++];
                arr[++ i] = '^';
            }
            int[] count = new int[arr.length];
            int maxLen = 0;
            int currLen = 0;
            int center = 0;
            int upper = len;
            while (center < upper) {
                // expand
                int half = currLen >> 1;
                int left = center - half;
                int right = center + half;
                while (left - 1 >= 0 && right + 1 < len && arr[left - 1] == arr[right + 1]) {
                    left --;
                    right ++;
                }
                count[center] = right - left + 1;
                
                // update result
                if (count[center] >= maxLen) {
                    l = left;
                    r = right;
                    upper = len - (maxLen >> 1);
                    maxLen = count[center];
                }
                
                // findNextCenter
                int nextCenter = -1;
                for (int i = 1 + center; i <= right; i ++) {
                    int mirror = count[(center << 1) - i];
                    int exRight = (mirror >> 1)  + i;
                    if (exRight == right) {
                        nextCenter = i;
                        currLen = mirror;
                        break;
                    } else if (exRight < right) {
                        count[i] = mirror;
                    } else {
                        count[i] = 1 + ((right - i) << 1);
                    }
                }
                if (nextCenter == -1) {
                    center = right + 1;
                    currLen = 0;
                } else {
                    center = nextCenter;
                }
            }
            return getResult(arr, l, r);
        }
        
        public String getResult(char[] arr, int left, int right) {
            char[] res = new char[(right - left) >> 1];
            int j = 0;
            for (int i = left + 1; i < right; i ++) {
                res[j++] = arr[i++]; 
            }
            return new String(res);
        }
    }
    

Log in to reply
 

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