186.md

186. 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 seperated by a single space.

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

Thinking Process

1. Reverse the entire string character by character
2. Reverse each words in the reversed string character by character

Code

public class Solution {
    public void reverseWords(char[] s) {
        reverse(s, 0, s.length - 1);
        //reverse each words
        int start = 0;
        for(int i = 0; i < s.length; i++){
            if(s[i] == ' '){
                reverse(s, start, i - 1);
                start = i + 1;
            }
        }
      	//reverse the last word
        reverse(s, start, s.length-1);
    }
    
    void reverse(char[] s, int from, int to){
        while(from < to){
            char temp = s[from];
            s[from++] = s[to];
            s[to--] = temp;
        }
    }
}

Complexity

1. Space complexity is O(1)
2. Time complexity is O(n) as the char array is reversed at most twice