(字符串 ) 151. 反转字符串中的单词 —

❓151. 反转字符串中的单词

难度：中等

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = “the sky is blue”
输出：“blue is sky the”

示例 2：

输入：s = " hello world "
输出：“world hello”
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = “a good example”
输出：“example good a”
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

$1 <= s.length <= 10^4$
s 包含英文大小写字母、数字和空格 ' '
s 中至少存在一个单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 $O (1)$ 额外空间复杂度的原地解法。

💡思路：

不使用辅助空间，那么只能在原字符串数组上下功夫了。

我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了：

移除多余空格；(一个erase本来就是 $O (n)$ 的操作, 所以这里使用快慢指针 平移，然后resize())
将整个字符串反转；
将每个单词反转。

🍁代码：(Java、C++)

Java

class Solution {public String reverseWords(String s) {StringBuilder sb = new StringBuilder();int start = 0, end = s.length() - 1;while(s.charAt(start) == ' ') start++;while(s.charAt(end) == ' ') end--;while(start <= end){//删除空格char c = s.charAt(start);if(c != ' ' || sb.charAt(sb.length() - 1) != ' ') sb.append(c);start++;}sb.reverse();//整个字符串反转int n = sb.length();start = 0;for(int i = 0; i < n; i++){//反转每个单词while(i < n && sb.charAt(i) != ' ') i++;end = i - 1;while(start < end){char c = sb.charAt(start);sb.setCharAt(start, sb.charAt(end));sb.setCharAt(end, c);start++;end--;}start = i + 1;}return sb.toString();}
}

C++

class Solution {
public:string reverseWords(string s) {int slow = 0;for(int i = 0; i < s.size(); ++i){if(s[i] != ' '){//遇到非空格就处理，即向前移动，以删除所有空格if(slow != 0) s[slow++] = ' ';//在单词前添加空格while(i < s.size() && s[i] != ' '){//补上该单词，遇到空格说明单词结束s[slow++] = s[i++];}}}s.resize(slow);slow的大小即为去除多余空格后的大小reverse(s.begin(), s.end());//整个字符串反转for(int start = 0, i = 0; i <= s.size(); i++){//反转每个单词if(s[i] == ' ' || i == s.size()){reverse(s.begin() + start, s.begin() + i);start = i + 1;}}return s;}
};

🚀 运行结果：

在这里插入图片描述

🕔 复杂度分析：

时间复杂度： $O (n)$ ，其中 n 为输入字符串的长度。
空间复杂度： $O (1)$ 或 $O (n)$ ，取决于使用的语言中字符串类型的性质。如果字符串是可修改的（C++），那么我们可以直接在原字符串上修改，空间复杂度为 $O (1)$ ，（Java）否则需要使用 $O (n)$ 的空间将字符串临时转换为可以修改的数据结构（例如数组），空间复杂度为 $O (n)$ 。