Easy to understand Java one loop solution.

  • 0

    Simple java solution, just loop on only the first half of the string and compare it with the remaining half, when find a balance point, return the string plus the reverse of the second half remaining.

        public String shortestPalindrome(String input){
        	if(input.isEmpty() || input.length() ==1 || input.equals(new StringBuffer(input).reverse()))
        		return input;
        	int startPivot = input.length()/2;
        	for(int currentPivot =startPivot; currentPivot>0; currentPivot--){
        		// check balanced string including the pivot
        		if(isBalanced(input,currentPivot, currentPivot+1)){
        			return new StringBuffer(input.substring(currentPivot*2 +2)).reverse() + input;
        		else if(isBalanced(input,currentPivot-1, currentPivot+1)){
        			return new StringBuffer(input.substring(currentPivot*2+1)).reverse() + input;
        	return new StringBuffer(input.substring(input.charAt(0)== input.charAt(1)? 2:1)).reverse() + input;
        private boolean isBalanced(String input, int rightPointer, int leftPointer)
        while(rightPointer>=0&& leftPointer<input.length() && input.charAt(rightPointer) == input.charAt(leftPointer)){
        return rightPointer<0;    	

Log in to reply

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