代码随想录算法训练营第八天| 151.翻转字符串里的单词

151.翻转字符串里的单词

文章链接：https://programmercarl.com/0151.翻转字符串里的单词.html#思路
视频链接：https://www.bilibili.com/video/BV1uT41177fX/?vd_source=6cb513d59bf1f73f86d4225e9803d47b
题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

class Solution {
public:
    //移除多余空格
    void removeExtraSpace(string &s){
        //使用快慢指针
        int slow=0;
        for(int i=0;i<s.size();i++){
            if(s[i]!=' '){
                if(slow!=0){  //如果不是第一个元素，则向前面加一个空格
                    s[slow++]=' ';
                }
                while(s[i]!=' '&&i<s.size()){
                    s[slow++]=s[i++];
                }
            }
        }
        s.resize(slow); //注意这里要缩减s的长度，slow后面的元素没有用的部分
    }
    //翻转
    void reverse(string &s,int start,int end){
        for(int i=start,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
    string reverseWords(string s) {
        removeExtraSpace(s); //移除不必要的空格
        reverse(s,0,s.size()-1);//对整个字符串进行翻转
        //对每个单词进行翻转
        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;
        
    }
};