186. Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Solution:

1. Reverse the entire array.

2. Go through the array, when we find a space, we know the start and end of a word. Reverse it.

3. Reverse the last word. (This is also the cast that the array has only one word.)



Code:

public class Solution {
    public void reverseWords(char[] s) {
        int n = s.length;
        
        reverse(s, 0, n - 1);
        
        int start = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') {
                reverse(s, start, i - 1);
                start = i + 1;
            } 
        }
        
        reverse(s, start, n - 1);
    }
    
    public void reverse(char[] arr, int i, int j) {
        while (i < j) {
            char tmp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = tmp;
        }
    }
}