186-reverse-words-in-a-string-ii

Question

https://leetcode.com/problems/reverse-words-in-a-string-ii/description/

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.

Example:

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

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

Thought Process

1. Reverse and Two Pointers
   1. We first reverse the whole string
   2. Then when we encounter a space, we reverse the start to the last position, so we "correct" the order
   3. Time complexity O(n)
   4. Space complexity O(1)

Solution

class Solution {
    public void reverseWords(char[] str) {
        int n = str.length;
        reverse(str, 0, n - 1);
        int start = 0, end = 0;
        while (end < n) {
            if (str[end] == ' ') {
                reverse(str, start, end - 1);
                start = end + 1;
            }
            end++;
        }
        reverse(str, start, end - 1);
    }

    private void reverse(char[] str, int i, int j) {
        while (i < j) {
            char tmp = str[i];
            str[i] = str[j];
            str[j] = tmp;
            i++;
            j--;
        }
    }
}

Additional