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

# 0151. Reverse Words in a String

<https://leetcode.com/problems/reverse-words-in-a-string>

## Description

Given an input string `s`, reverse the order of the **words**.

A **word** is defined as a sequence of non-space characters. The **words** in `s` will be separated by at least one space.

Return *a string of the words in reverse order concatenated by a single space.*

**Note** that `s` may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

**Example 1:**

```
**Input:** s = "the sky is blue"
**Output:** "blue is sky the"
```

**Example 2:**

```
**Input:** s = "  hello world  "
**Output:** "world hello"
**Explanation:** Your reversed string should not contain leading or trailing spaces.
```

**Example 3:**

```
**Input:** s = "a good   example"
**Output:** "example good a"
**Explanation:** You need to reduce multiple spaces between two words to a single space in the reversed string.
```

**Example 4:**

```
**Input:** s = "  Bob    Loves  Alice   "
**Output:** "Alice Loves Bob"
```

**Example 5:**

```
**Input:** s = "Alice does not even like bob"
**Output:** "bob like even not does Alice"
```

**Constraints:**

* `1 <= s.length <= 104`
* `s` contains English letters (upper-case and lower-case), digits, and spaces `' '`.
* There is **at least one** word in `s`.

\*\*Follow-up:\*\*If the string data type is mutable in your language, can you solve it **in-place** with `O(1)` extra space?

## ac

it's so stupid not being able to use trim(), split().

```java
public class Solution {
    public String reverseWords(String s) {
        // edge case
        if (s.length() == 0) return "";

        char[] chars = s.toCharArray();

        // clean space
        int len = 0;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == ' ' && (i == 0 || chars[i-1] == ' ')) continue;
            chars[len] = chars[i];
            len++;
        }

        if (len == 0) return ""; // all empty

        if(chars[len-1] == ' ') len = len - 1;

        // reverse whole string
        reverse(chars, 0, len-1);

        /// reverse each word
        int k = 0, j = 0;
        for (; k < len; k++) {
            if (chars[k] != ' ') continue;
            reverse(chars, j, k-1);
            j = k+1;
        }
        if (k == len) reverse(chars, j, k-1);

        // append to sb
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < len; i++) {
            sb.append(chars[i]);
        }

        return sb.toString();
    }

    private void reverse(char[] chars, int s, int e) {
        while (s < e) {
            char tmp = chars[s];
            chars[s] = chars[e];
            chars[e] = tmp;
            s++;
            e--;
        }
    }
}
```