Java in-place 3 ms solution | beats 88%


  • 10
    R
    class Solution {
    

    Blockquote

    /**
    In place word reverse ignoring new String object built. Idea is to reverse each word then reverse the whole string. Space is tackled by trimming and shifting chars to left i.e if i points to space and i-1 also point to space shift chars starting from i+1 left by one place. Decrement end pointer pointing to end of string.

    Example steps:

    1. s =" Hello World "

    2. Trim s = "Hello World"

    3. Reverse each word - s ="olleH dlroW"

    4. Reverse whole string s= "World Hello"

    @param s

    @return reversed string object
    */

    Blockquote

    public static String reverseWords(String s) {
    	if (s == null)
    		return null;
    
    	char[] str = s.toCharArray();
    	int start = 0, end = str.length - 1;
    
    	// Trim start of string
    	while (start <= end && str[start] == ' ')
    		start++;
    
    	//Trim end of string
    	while (end >= 0 && str[end] == ' ')
    		end--;
    
    	if (start > end)
    		return new String("");
    
    	int i = start;
    	while (i <= end) {
    		if (str[i] != ' ') {
    			// case when i points to a start of word -  find the word reverse it
    			int j = i + 1;
    			while (j <= end && str[j] != ' ')
    				j++;
    			reverse(str, i, j - 1);
    			i = j;
    		} else {
    			if (str[i - 1] == ' ') {
    				//case when prev char is also space - shift char to left by 1 and decrease end pointer
    				int j = i;
    				while (j <= end - 1) {
    					str[j] = str[j + 1];
    					j++;
    				}
    				end--;
    			} else
    				// case when there is just single space
    				i++;
    		}
    	}
    	//Now that all words are reversed, time to reverse the entire string pointed by start and end - This step reverses the words in string
    	reverse(str, start, end);
    	// return new string object pointed by start with len = end -start + 1
    	return new String(str, start, end - start + 1);
    }
    
    private static void reverse(char[] str, int begin, int end) {
    	while (begin < end) {
    		char temp = str[begin];
    		str[begin] = str[end];
    		str[end] = temp;
    		begin++;
    		end--;
    	}
    }
    

    }


  • 0
    D

    Isn't

    return new String(str, start, end - start + 1);
    

    using more space?


  • 0
    R

    @diaosi123 - Yes it is, since strings in java are immutable object there is no other option I guess. I specified this in the blockquote as well


Log in to reply
 

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