# 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⁴</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

# 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++

// 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"