---
# System prepended metadata

title: LC 151. Reverse Words in a String
tags: [medium, leedcode, python, c++]

---

# LC 151. Reverse Words in a String

### [Problem link](https://leetcode.com/problems/reverse-words-in-a-string/)

###### tags: `leedcode` `medium` `python` `c++`

Given an input string <code>s</code>, reverse the order of the  **words** .

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

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

 **Note**  that <code>s</code> 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.
```

 **Constraints:** 

- <code>1 <= s.length <= 10<sup>4</sup></code>
- <code>s</code> contains English letters (upper-case and lower-case), digits, and spaces <code>' '</code>.
- There is  **at least one**  word in <code>s</code>.


**Follow-up:** If the string data type is mutable in your language, canyou solve it **in-place** with `O(1)` extra space?
## Solution 1
#### Python
```python=
# Mar 23, 2023
class Solution:
    def reverseWords(self, s: str) -> str:
        s_list = [i for i in s.split(" ") if len(i) > 0]
        
        return " ".join(s_list[::-1])
```
#### C++
```cpp=
// Nov 20, 2023
class Solution {
public:
    void trim(string &s) {
        int left = 0;

        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                if (left != 0) {
                    s[left++] = ' ';
                }
                while (i < s.size() && s[i] != ' ') {
                    s[left++] = s[i++];
                }
            }
        }
        s.resize(left);
    }

    string reverseWords(string s) {
        trim(s);
        reverse(s.begin(), s.end());

        int idx = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == ' ') {
                reverse(s.begin() + idx, s.begin() + i);
                idx = i + 1;
            }
        }
        reverse(s.begin() + idx, s.end());
        return s;
    }
};
```

>### Complexity
>|                     | Time Complexity | Space Complexity |
>| ------------------- | --------------- | ---------------- |
>| Solution 1(c++)     | O(n)            | O(1)             |
>| Solution 1(python)  | O(n)            | O(n)             |

## Note
[reference](https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0151.%E7%BF%BB%E8%BD%AC%E5%AD%97%E7%AC%A6%E4%B8%B2%E9%87%8C%E7%9A%84%E5%8D%95%E8%AF%8D.md)

c++的std::reverse是左閉右開的形式.

trim: "  the sky is blue  " => "the sky is blue"
reverse: "the sky is blue" => "eulb si yks eht"
code最後一段: "eulb si yks eht" => "blue is sky the"
