翻转字符串里面的单词---leetcode 151题

 这道题分步骤来写：
首先要去除多余的空格：有两种方法

        第一种：快慢指针法：时间复杂度低但是思路复杂

void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0; 
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.size(); fastIndex++) {
            
            if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') {
                continue;
            } else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { 
            s.resize(slowIndex - 1);
        } else {
            s.resize(slowIndex); 
        }
    }

        第二种：直接遍历字符串，使用erase函数删除，思路简单，时间复杂度高

void removeExtraSpaces(string& s) {
        for (int i = s.size() - 1; i > 0; i--) {
            if (s[i] == s[i - 1] && s[i] == ' ') {
                s.erase(s.begin() + i);
            }
        }
        // 删除字符串最后面的空格
        if (s.size() > 0 && s[s.size() - 1] == ' ') {
            s.erase(s.begin() + s.size() - 1);
        }
        // 删除字符串最前面的空格
        if (s.size() > 0 && s[0] == ' ') {
            s.erase(s.begin());
        }
    }

 去除空格后开始执行下一步，首先反转整个字符串，然后再字符串最后插入一个空格（关键一步，因为要通过空格来识别每个单词），然后定义两个指针start，end，和一个bool类型（用来判断是否进入一个单词）。接着开始for循环，第一个if，判断进入第一个单词，让start指向单词开头，第二个if，代表当i到达空格的时候，这时第一个单词遍历结束，然后调用reverse翻转第1个单词。之后继续循环进入第二个单词，重复上述 *** 作，直到i指向最后的空格（体现了前边加空格的作用），将最后一个单词翻转完毕，接着再把最后一个空格删除，然后输出s。

string reverseWords(string s) {
        removeExtraSpaces(s);//调用去除空格函数
        reverse(s.begin(),s.end());
        s.push_back(' ');
        int start = 0;
        int end = 0;
        bool entry = false;
        for(int i = 0; i

class Solution {
public:
 void removeExtraSpaces(string& s) {
        int slowIndex = 0, fastIndex = 0; 
        while (s.size() > 0 && fastIndex < s.size() && s[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < s.size(); fastIndex++) {
            
            if (fastIndex - 1 > 0 && s[fastIndex - 1] == s[fastIndex] && s[fastIndex] == ' ') {
                continue;
            } else {
                s[slowIndex++] = s[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') { 
            s.resize(slowIndex - 1);
        } else {
            s.resize(slowIndex); 
        }
    }
    string reverseWords(string s) {
        removeExtraSpaces(s);
        reverse(s.begin(),s.end());
        s.push_back(' ');
        int start = 0;
        int end = 0;
        bool entry = false;
        for(int i = 0; i

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] = ' ';
                    idx++;
                }
                int end = start;
                while(end < n && s[end] != ' ') 
                {
                    s[idx] = s[end];
                    idx++;
                    end++;
                }
                reverse(s.begin()+idx-(end-start),s.begin()+idx);
                start = end;
            }
        }
        s.erase(s.begin()+idx,s.end());
        return s;
    }
};