题目描述

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

为简单起见，标点符号和普通字母一样处理。

例如输入字符串”I am a student.”，则输出”student. a am I”。

样例

输入："I am a student."

输出："student. a am I"

算法1

(双指针，vector)

1. 看了y总的题解，用了reverse()，我用的vector达到了同样的效果，也AC了。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    string reverseWords(string s) {
        string res;
        vector<string> ves;
        for(int i = 0; i < s.size(); i ++)
        {
            int j = i;
            while(j < s.size() && s[j] != ' ')
            {
                res += s[j];
                j ++;
            }
            ves.push_back(res);
            res.clear();
            i = j;
        }

        string ans;
        for(int k = ves.size() - 1; k >= 0; k --)
        {
            ans += ves[k];
            if(k > 0) ans += " ";
        }

        return ans;
    }
};

算法2

(双指针，reverse)

1. 看了y总的题解，有个地方不太理解。
2. 第一次翻转前是I，翻转后应该是I，但是我打印出来好像并不是这样，怎么回事呀？

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    string reverseWords(string s) {
        for(int i = 0; i < s.size(); i ++)
        {
            int j = i;
            while(j < s.size() && s[j] != ' ') j ++;
            // reverse(s.begin() + i, s.end() + j);
            reverse(s.begin() + i, s.begin() + j); 
            // cout << s << "--------" << endl;
            i = j;
        }
        reverse(s.begin(), s.end());
        return s;
    }
};