My O(n) Java Solution, 9ms ,O(n) Space


  • 0
    U
    public String reverseWords(String s) {
    	char[] array = s.toCharArray();
    	int startIndex = 0;
    	int endIndex = 0;
    	boolean start = false;
    	boolean end = false;
    	for(int i = 0 ; i < array.length ; i++){
    		 if(array[i] != ' '){
    			 if(!start){
    				 startIndex = i;
    			 }
    			 start = true;
    			 if(!end){
    				 endIndex = i;
    			 }
    		 }else{
    			 if(start){
    				 end = true;
    			 }
    		 }
    		 
    		 if(start &&(end || ((i == array.length - 1) && !end ))){
    			 reverse(array, startIndex, endIndex);
    			 start = end = false;
    		 }
    	}
    	
    
    	StringBuilder sb = new StringBuilder();
    	boolean addSpace = false;
        for(int i = array.length - 1 ; i >= 0 ; i -- ){
        	char c =  array[i];
        	
        	if(c != ' '){
        		sb.append(c);
        		addSpace = true;
        	}else{
        		if(addSpace){
        			sb.append(c);
        			addSpace = false;
        		}
        	}       	
        }
        return sb.toString().trim();
    	
    }
    
    private void reverse(char[] array ,int start,int end){
    	
    	char temp ;
    	while(start < end){
    		temp = array[start];
    		array[start] = array[end];
    		array[end] = temp;
    		start ++;
    		end --;
    	}
    }

Log in to reply
 

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