186. Reverse Words in a String II

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?

Related problem: Rotate Array

Solution

public class Solution {
      public void reverseWords(char[] s) {
        if (s == null || s.length <= 1) return;

        int start = 0;
        int end = 0;
        boolean flag = false;
        while (end < s.length) {
            if (s[end] == ' ') {
                reverse(s, start, end - 1);
                start = end + 1;
            }
            end++;
        }

        reverse(s, start, s.length-1);
        reverse(s,0, s.length-1);
    }

    private void reverse(char[] s, int start, int end) {
        while (start < end) {
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start++;
            end--;
        }
    }

}