题目描述

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

示例 1：

输入：s = “Let’s take LeetCode contest”
输出：“s’teL ekat edoCteeL tsetnoc”

示例 2:

输入： s = “God Ding”
输出：“doG gniD”

提示：

1 <= s.length <= 5 * 104
s 包含可打印的 ASCII 字符。
s 不包含任何开头或结尾空格。
s 里 至少 有一个词。
s 中的所有单词都用一个空格隔开。

题目链接：https://leetcode-cn.com/problems/reverse-words-in-a-string-iii

思路分析

思路一：开辟新的字符串进行操作

首先开辟一个字符串

然后从头到尾遍历原字符串，直到找到一个空格“ ”为止

这时我们可以找到一个单词，并能够得到单词的起止位置

随后根据起止位置将单词逆序放到字符串中即可

如上所述，直到遍历完成字符串，就能得到答案了

时间复杂度：O(N)

空间复杂度：O(N)

思路一的代码：

class Solution {
public:
    string reverseWords(string s) {
        string ans;//用于存储答案的字符串
        int length = s.length();
        int i = 0;
        while (i < length) {//循环遍历整个字符串
            int start = i;//每次循环开始时，记录下当前位置，作为该单词的起始位置
            while (i < length && s[i] != ' ') {//i向右移动，直到找到一个空格
                i++;
            }//循环结束后，这个i就指向了该单词的结束位置的后一位了
            for (int p = start; p < i; p++) {//p指针从结束位置向起始位置移动，循环将字符添加到答案字符串中
                ans.push_back(s[start + i - 1 - p]);//起始+终末-p，其中终末=i-1
            }
            if (i < length && s[i] == ' ') {//当i小于字符串长度且i指向空格时
                i++;//i向后移动一位
                ans.push_back(' ');//向ans中末尾添加空格
            }//没有这一步的话，将无法跳出循环
//另外，题目中指出“每个单词之间只有一个空格”，如果每个单词之间有多个空格，则需要将最后一个if改成while
        }
        return ans;
    }
};

思路二：原地解法(Recommended)：

可以直接在原字符串上进行操作，以避免额外的空间开销，值得注意的是本解法在字符串不可变的语言中不可使用。（字符串可变的语言有：C/C++,Ruby,PHP,Swift；字符串不可变的语言有：Java,Python,C#,JavaScript,GO）

本思路在上面思路的基础上，稍作更改即可

在找到每个单词的起始位置和结束位置后，交换第一个字符和倒数第一个字符，直到程序结束即可

思路二的代码：

class Solution {
public:
    string reverseWords(string s) {
        int len = s.length();
        int i = 0;//i充当指针的角色，用于遍历字符串s
        while (i < len) {//循环整个字符串
            int start = i;//首先定义start指针指向本次循环的开始，记录单词的起始位置
            while (i < len && s[i] != ' ') {//循环，直到指针i指到一个空格或超出范围
                i++;
            }
            int end = i - 1;//i指向空格，那么本次循环找到的单词的结尾就是i-1
            while (start < end) {//循环交换
                swap(s[start], s[end]);
                start++;
                end--;
            }
            while (i < len && s[i] == ' ') {//如果s指向空格，则跳过空格
                i++;
            }
        }
        return s;
    }
};

总结：遇到反转问题，要能想到使用双指针解决此类问题。