给你一个字符串 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 <= 104
s
包含英文大小写字母、数字和空格' '
s
中 至少存在一个 单词
进阶:如果字符串在你使用的编程语言中是一种可变数据类型,请尝试使用 O(1)
额外空间复杂度的 原地 解法。
先看我自己的代码:
class Solution {
public:
string reverseWords(string s) {
stack<string> strs;
string th;
int len=s.size();
for(int i=0;i<len;i++)
{
if(s[i]==' ')
{
if(th!="")
strs.push(th);
th="";
continue;
}
else{
th+=s[i];
}
if(i==len-1)
{
strs.push(th);
}
}
string str1;
while(!strs.empty())
{
if(strs.size()==1)
{
str1+=strs.top();
strs.pop();
}
else{
str1+=strs.top();
str1+=" ";
strs.pop();
}
}
return str1;
}
};
我的问题就是,很多题能做出来,就是算法很奇怪,所谓奇怪,就是不会简化代码,看看官方解答:
先看人家写的Python:
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(reversed(s.split()))
精简优雅。
再看人家的C++:
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] != ' ') {
// 填一个空白字符然后将idx移动到下一个单词的开头位置
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,去找下一个单词
start = end;
}
}
s.erase(s.begin() + idx, s.end());
return s;
}
};
作用就是先将整个字符串进行翻转,然后对每一个单词进行翻转。