题目描述

给定一个字符串 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;
    }
};

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

Q.E.D.