> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/string/reverse-words-in-a-string-ii.md).

# 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--;
    }
}
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/string/reverse-words-in-a-string-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.