Beat 99% java solution


  • 2
    N
    public String shortestPalindrome(String s) {
        if(s==null||s.length()==0){
            return s;
        }
        char[] arr = s.toCharArray();
        StringBuilder sb = new StringBuilder();
        int cent = getCentralPoint(arr);
        for(int i = arr.length-1;i>=cent;i--){
            sb.append(arr[i]);
        }
        sb.append(s);
        return sb.toString();
    }
    
    private int getCentralPoint(char[] arr){
        int mid = (arr.length-1)/2;
        int i = mid;
        int j = mid;
        while(i>=0){
        	i = mid;
        	j = mid;
            while(i>=0&&arr[i]==arr[mid]){
                i--;
            }
            while(j<arr.length&&arr[j]==arr[mid]){
                j++;
            }
            int cp = centralPoint(arr,i,j);
            if(cp!=-1){
            	return cp;
            }
            mid = i;
        }
        return 0;
    }
    
    private int centralPoint(char[] arr,int i,int j){
        while(i>=0&&j<arr.length){
            if(arr[i]!=arr[j]){
                return -1;
            }
            i--;
            j++;
        }
        return i!=-1?-1:j;
    }

  • 1
    L

    It is a great solution. But the centralpoint method is kind of ambiguous, I think it should be the rightmost point of a palindrome.


  • 0
    S

    beat 99% but if you try test case "cababababababab...a", it takes more than 100 ms.


Log in to reply
 

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