151. 反转字符串中的单词

Problem: 151. 反转字符串中的单词

Reference

https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2361551/151-fan-zhuan-zi-fu-chuan-zhong-de-dan-c-yb1r/?envType=study-plan-v2&envId=top-interview-150

思路

主要是参照上面的写法，看他的动图很快可以看明白。

但是C++没有trim，需要自己实现。

需要注意的是，最后剔除完前后空格需要resize，注意剔除完之后的字符串大小。

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]

class Solution {

public:

    string reverseWords(string s) {

        trim(s);

        std::cout << s.size() << endl;

        string res;

        int j = s.size() - 1, i = s.size() - 1;

        while (i >= 0) {

            while (i >= 0 && s[i] != ' ')

                i--;

            res += s.substr(i + 1, j - i);

            res += ' ';

            while (i >= 0 && s[i] == ' ')

                i--;

            j = i;

        }

        trim(res);

        return res;

    }

  

    void trim(string& s) {

        int i = 0, j = s.size() - 1;

        while (s[i] == ' ')

            i++;

        while (s[j] == ' ')

            j--;

        s = s.substr(i, j - i + 1);

        s.resize(j - i + 1);

    }

};