题目描述

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

样例

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

注意

• 在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

算法

(模拟) $O(n)$

1. 按照以空格分隔的方式将单词提取出来放到一个字符串数组中。
2. 对字符串数组中的每个单词进行 reverse 操作后，再将其拼接为以空格分隔的完整字符串即可。

时间复杂度

• 每个字符仅遍历常数次，故时间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    string reverseWords(string s) {
        vector<string> words;
        int last = 0;
        for (int i = 0; i < s.length(); i++)
            if (s[i] == ' ') {
                words.push_back(s.substr(last, i - last));
                last = i + 1;
            }
        words.push_back(s.substr(last, s.length() - last));

        string ans = "";
        for (int i = 0; i < words.size(); i++) {
            reverse(words[i].begin(), words[i].end());
            ans += words[i];
            if (i < words.size() - 1)
                ans += " ";
        }

        return ans;
    }
};