题目
给你一个字符串 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 <= 104s包含英文大小写字母、数字和空格' 's中 至少存在一个 单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。
解答
- 暴力解法
大致思路：将字符串中的每个单词放入动态数组中，然后将动态数组倒序遍历得到结果字符串，最后返回结果字符串，C++代码实现如下：
class Solution {
public:
string reverseWords(string s) {
// 特判：如果s的长度为1，则只包含一个单词，此时直接返回s即可
if (s.length() == 1) return s;
// 新建s_vec动态数组，元素类型为string
vector<string> s_vec;
// 定义left，它是指向字符串里第一个单词的第一个字母的指针
int left = 0; // left的初始化
while (s[left] == ' ') {
left++; // 防止字符串一开始就是空格
}
// 开始循环
for (int i = left; i < s.length(); i++) {
// 当i指向一个单词右边的第一个空格或者字符串的最后一个元素时
if (s[i] == ' ' || i == s.length() - 1) {
if (i == s.length()-1) i++; // 当i指向字符串的最后一个字母时，需要自增1，否则无法通过substr获得子串
string temp = s.substr(left, i - left); // 使用substr获得子串
s_vec.push_back(temp); // 将子串push进动态数组s_vec中
while (s[i] == ' ' && i < s.length()) {
i++; // 令i从其之后的第一个非空字母开始遍历
}
left = i; // 更新left的值
}
}
if (s[s.length()-1] != ' ' && s[s.length()-2] == ' ') { // 针对字符串最后的一个单词只有一个字母的特判
string temp = s.substr(s.length()-1);
s_vec.push_back(temp);
}
int n = s_vec.size(); // 获取动态数组的大小（也就是总的单词个数）
string result; // 定义结果字符串
for (int i = n - 1; i >= 0; i--) { // 反向遍历，将结果同result相加
if (i == n - 1) { // 第一个单词前无需加空格
result = result + s_vec[i];
}
else { // 其他单词在同result合并前需要先加一个空格
result = result + " " + s_vec[i];
}
}
return result; // 返回result字符串
}
};- 空间复杂度为O(1)的解法
- 将整个字符串进行反转
- 将反转后的字符串的每个单词进行反转
- 去除字符串中多余的空格
class Solution {
public:
string reverseWords(string s) {
reverse(s.begin(), s.end()); // 翻转整个字符串
int n = s.size();
int idx = 0;
for (int start = 0; start < n; ++start) {
if (s[start] != ' ') { // 找到单词的起始位置
if (idx != 0) s[idx++] = ' '; // 添加单词间空格
int end = start;
while (end < n && s[end] != ' ') s[idx++] = s[end++]; // 翻转单词
reverse(s.begin() + idx - (end - start), s.begin() + idx); // 翻转单词
start = end;
}
}
s.erase(s.begin() + idx, s.end()); // 删除多余的空格
return s;
}
};当我们调用reverse函数时，它会将字符串中的字符进行翻转。例如，如果我们有一个字符串”hello”，那么调用reverse函数后，它会变成”olleh”。在这个题目中，我们需要将整个字符串进行翻转，所以我们调用了reverse(s.begin(), s.end())函数来实现这个功能。