# Reverse Words in a String II

Given an input string, reverse the string word by word.

**Example:**

```
Input:  
["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]

Output: 
["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]
```

**Note:** 

* A word is defined as a sequence of non-space characters.
* The input string does not contain leading or trailing spaces.
* The words are always separated by a single space.

**Follow up:** Could you do itin-placewithout allocating extra space?

**Topics**: Two Pointers, String

## Analysis

分析见[Reverse Words in a String](https://github.com/aaronice/lintcode/tree/bbbb974440d4233e80bad25778c3733867e871db/string/two_pointers/reverse-words-in-a-string.md)

同样是多步翻转+Two Pointer进行逆序、翻转操作。

在`void reverseEachWords(char[] str)`中，快指针找到word结尾后的index，满指针指向word的开始第一个index。

## Solution

Two-Pointer + Multi-reversal - O(n) time, O(1) space (In-place) - (5ms AC)

```java
class Solution {
    public void reverseWords(char[] str) {
        // reverse the whole input 
        reverse(str, 0, str.length - 1);

        // reverse each individual word
        reverseEachWords(str);
    }

    void reverse(char[] str, int s, int t) {
        while (s < t) {
            char tmp = str[s];
            str[s] = str[t];
            str[t] = tmp;
            s++;
            t--;
        }
    }

    void reverseEachWords(char[] str) {
        int i = 0, j = 0; 
        int n = str.length;
        while (i < n && j < n) {
            while (i < n && str[i] == ' ') {
                i++;
            }
            j = i;
            while (j < n && str[j] != ' ') {
                j++;
            }
            reverse(str, i, j - 1);
            i = j;
        }
    }
}
```

This solution (by [@siyang3](https://leetcode.com/problems/reverse-words-in-a-string-ii/discuss/53775/My-Java-solution-with-explanation/55063)) takes advantage of the conditions in the problem: 1. The input string does not contain leading or trailing spaces. 2. The words are always separated by a single space.

```java
public void reverseWords(char[] s){
    reverseWords(s,0,s.length-1);
    for(int i = 0, j = 0;i <= s.length;i++){
        if(i==s.length || s[i] == ' '){
            reverseWords(s,j,i-1);
            j = i+1;
        }
    }
}

private void reverseWords(char[] s, int begin, int end){
    while(begin < end){
        char c = s[begin];
        s[begin] = s[end];
        s[end] = c;
        begin++;
        end--;
    }
}
```