思路
单词前面有空格,后面有空格,中间有多余空格
1去掉多余空格
2全部翻转
3单词内部翻转
这里也用双指针,一个start,一个end,当end遇到空格(即一个单词的结尾)或者是到达字符串s的末尾时
reverse(s,start,end-1)
//去除空格逻辑,双指针
void removeEmpty(string &s)
{int slow = 0;for(int fast =0;fast<s.size();fast++)
{//这里容易遗忘的是for循环里大的逻辑是 s[fast] !=' ' 就是说跳过前面和中间的空格if(s[fast] !=' '){if(slow != 0)//已经有一个单词了,这时需要添加一个空格{s[slow++] = ' ';}//如果遇到单词,将fast指针的部分复制到slow指针位置while(fast<s.size() && s[fast] != ' '){s[slow++] = s[fast++];}}
}
s.resize(slow);
}
//整体逻辑,先翻转,再去空格,再单词内部翻转
string reverseWords(string s)
{reverse(s,0,s.size()-1);removeEmpty(s);int start=0;for(int i = 0;i<=s.size();i++){if(i == s.size() ||s[i] ==' '){reverse(s,start,i-1);start = i+1;}}return s;
}
整体代码如下
// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem151.h"using namespace std;
// @before-stub-for-debug-end/** @lc app=leetcode.cn id=151 lang=cpp** [151] 反转字符串中的单词*/// @lc code=start
class Solution
{
public:
//翻转逻辑
void reverse(string &s,int start,int end)
{while(start<end){swap(s[start],s[end]);start++;end--;}
}
//去除空格void removeEmpty(string &s)
{//双指针int slow = 0;for(int fast = 0;fast<s.size();fast++){if(s[fast]!=' '){if(slow != 0){s[slow++] = ' ';}while(s[fast]!= ' ' && fast<s.size()){s[slow++] = s[fast++]; }}}s.resize(slow);
}
//单词内部翻转string reverseWords(string s) {//先整体翻转,再去空格//再单词内部翻转,双指针reverse(s,0,s.size()-1);removeEmpty(s);int start = 0;for(int i = 0;i<=s.size();i++){if(s[i] == ' '|| i == s.size()){reverse(s,start,i-1);start = i+1;}}return s;}
};
// @lc code=end