[leetcode]151.翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明：

输入字符串 s 可以在前面、后面或者单词间包含多余的空格。

翻转后单词间应当仅用一个空格分隔。

翻转后的字符串中不应包含额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"
           

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：输入字符串可以在前面或者后面包含多余的空格，但是翻转后的字符不能包括。
           

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，将翻转后单词间的空格减少到只含一个。
           

示例 4：

输入：s = "  Bob    Loves  Alice   "
输出："Alice Loves Bob"
           

示例 5：

输入：s = "Alice does not even like bob"
输出："bob like even not does Alice"
           

提示：

1 <= s.length <= 104
s 包含英文大小写字母、数字和空格 ' '
s 中 至少存在一个 单词
           

进阶：

请尝试使用 O(1) 额外空间复杂度的原地解法。
           

思路：

本题要求空间复杂度O(1)，所以不能使用split分割字符串，在重新叠加成一个新的字符串。

1.移除多余空格。

1）删除掉字符串开头的所有空格。2）单词与单词之间只保留一个空格。3）处理结束之后删掉字符串最后面的空格（如果存在）

使用双指针法，时间复杂度O(n)，空间复杂度O(1)

void removeExtraSapces(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];
            slowIndex++;
        }
    }

    if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') {
        //去掉末尾的空格(如果只有一个空格不能删除)
        s.resize(slowIndex - 1);
    } else {
        s.resize(slowIndex);
    }
}
           

2.反转整个字符串 时间复杂度O(n)，空间复杂度O(1)

3.将每个单词进行反转 时间复杂度O(n)，空间复杂度O(1)

于是就可以在原地实现要求

区间反转字符串思路：

[leetcode]344.反转字符串

[leetcode]541.反转字符串（2）

void reverse(string& s, int start, int end) {
    int i = start, j = end;
    while (i < j) {
        swap(s[i], s[j]);
        i++;
        j--;
    }
}
           

AC代码：（C++）

class Solution {
   public:
    void reverse(string& s, int start, int end) {
        int i = start, j = end;
        while (i < j) {
            swap(s[i], s[j]);
            i++;
            j--;
        }
    }
    void removeExtraSapces(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];
                slowIndex++;
            }
        }

        if (slowIndex - 1 > 0 && s[slowIndex - 1] == ' ') {
            //去掉末尾的空格(如果只有一个空格不能删除)
            s.resize(slowIndex - 1);
        } else {
            s.resize(slowIndex);
        }
    }
    string reverseWords(string s) {
        removeExtraSapces(s);
        reverse(s, 0, s.size() - 1);
        int start = 0, end = 0;
        bool entry = false;
        for (int i = 0; i < s.size(); i++) {
            //反转单词
            if (!entry) {
                start = i;  //单词起始位置
                entry = true;
            }
            if (entry && s[i] == ' ' && s[i - 1] != ' ') {
                end = i - 1;  //单词终止位置
                entry = false;
                reverse(s, start, end);
            }
            if (entry == true && (i == (s.size() - 1)) && s[i] != ' ') {
                end = i;
                entry = false;
                reverse(s, start, end);
            }
        }
        return s;
    }
};