151. 反转字符串中的单词

思路

题目要求实现字符串中单词顺序的反转功能。

关键步骤包括：预处理空格、整体反转、按单词局部反转

先预处理空格，遍历字符串，遇到连续空格就删除后一个并让i不更新，首尾特判一下。然后整体反转字符串，这时单词顺序反转了，但里面字母的顺序也反转了，再逐个反转每个单词，把单词中字母的顺序调整对。

通过双指针分段反转，时间复杂度O(n)，空间复杂度O（1）。

代码

string reverseWords(string s) {
int a;
for(int i=0;i<=s.size()-1;i++) {
if(i<s.size()-1&&s[i]==' '&&s[i+1]==' ') {
s.erase(i+1,1);
i–;
}
}
if(s[0]==' ') {
s.erase(0,1);
}
if(s[s.size()-1]==' ') {
s.erase(s.size()-1,1);
}
reverse(s.begin(),s.end());
a=0;
for(int i=0;i<=s.size()-1;i++) {
if(s[i]==' ') {
reverse(s.begin()+a,s.end()-(s.size()-i));
a=i+1;
}
}
reverse(s.begin()+a,s.end());
return s;
}
};