Easy to understand Java one loop solution.


  • 0
    A

    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)){
        	rightPointer--;
        	leftPointer++;
        	continue;
        }
        return rightPointer<0;    	
        }
    

Log in to reply
 

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