反转字符串中的单词--力扣151

题目

思路

题目的难点在于首先要清除多余的空格，并且单词之间要留一个空格，首单词前和末尾单词后不能有多余空格。我们使用双指针去除所有的空格，然后在处理完一个单词后手动加一个单词。具体思路是当快指针不等于空格时，赋值给慢指针，然后快慢指针同时移动，当快指针等于空格时，慢指针不动，快指针循环移动，一直循环到不等于空格时，继续上述操作。每当处理完一个单词，此时慢指针手动加一个空格，已满足每个单词之间要有一个空格的要求。判断slow != 0，是因为开头有可能有多余的空格，此时不需要额外添加。

其次需要翻转，我们首先将s所有的字符整体翻转过来，然后逐个翻转单词。注意s的范围在0-s.size-1,而s.size()为\0。最后的for循环到s.size()是为了知道到末尾了，方便翻转最后一个单词。

代码

class Solution {
public:
    //翻转函数
    void reverse (string& s, int x, int y) {
        for (int i = x, j = y; i < j; i++, j--) {
            swap(s[i], s[j]);
        }
    }
    //删除多余的空格
    void deleteExtraSpaces (string& s) {
        //双指针法删除多余空格
        int slow = 0;
        for (int fast = 0; fast < s.size(); fast++) {
            if (s[fast] != ' ') {
                //删除所有空格，然后在相邻单词之间手动加一个空格。
                if (slow != 0) s[slow++] = ' ';
                while (fast < s.size() && s[fast] != ' ') {
                    s[slow++] = s[fast++];
                }
            }
        }
        s.resize(slow);
    }
    //翻转，先清除多余空格，翻转所有字符串，在单个翻转单词
    string reverseWords(string s) {
        deleteExtraSpaces(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);
                //下一个单词开始为i+1
                start = i + 1;
            }
        }
        return s;
    }
};