Leetcode 151.翻转字符串里的单词【C++】

地址：https://leetcode-cn.com/problems/reverse-words-in-a-string/

题目

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

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

示例 3：

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

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

• 请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

解题思路

做倒是做出来了，思路不复杂，但是代码极其复杂。

起初我的想法是写一个循环，同时从两头往中间遍历，一头找到一个单词就先停下来，等另一头也找到一个单词，然后对换，再继续找下一对单词前后对换。但是在我写代码的过程中，才慢慢发现，只要在原字符串上进行了对换，那么原本的索引 i ， j 就不再是正确的索引了，要搞清楚其中的变换关系还是挺复杂的。

后来我改为了两层循环，并且定义两个整型变量 lenl 和 lenr 分别表示前后两个单词的长度。外层循环从前往后遍历，找到一个单词就进入内层循环，内层循环从后往前遍历，找到一个单词后，进行前后对换，然后修改索引 i ， j 的值，并将 lenl 和 lenr 重新置为 0 ，继续查找下一个单词。

前面所做的工作只对单词进行了处理，字符串中的空格还没有处理。所以现在要分别删除首尾的空格以及将单词之间的多个空格压缩为一个。

代码

class Solution {
public:
    string reverseWords(string s) {
        int i = 0;
        int j = 1;
        int lenl = 0;//前单词长度
        int lenr = 0;//后单词长度
        while (i + j <= s.size())
        {
            //单词长度+1
            if (s[i] != ' ') {
                lenl++;
            }
            if (s[i] == ' ' && lenl != 0) {
                while (j + i <= s.size()) {
                    //单词长度+1
                    if (s[s.size() - j] != ' ') {
                        lenr++;
                    }
                    if (s[s.size() - j] == ' ' && lenr != 0) {
                        string tmp = s.substr(i - lenl, lenl);
                        //替换前单词
                        s.erase(i - lenl, lenl);
                        s.insert(i - lenl, s.substr(s.size() - j + 1, lenr));
                        //替换后单词
                        s.insert(s.size() - j + 1, tmp);
                        s.erase(s.size() - j + 1, lenr);
                        //重新设置i，j
                        i = i - lenl + lenr;
                        j = j - lenr + lenl;
                        //重置lenl和lenr
                        lenl = 0;
                        lenr = 0;
                        break;
                    }
                    j++;
                }
            }
            i++;
        }
        //去掉首尾空格
        while (s.size() > 0 && s.front() == ' ') {
            s.erase(0, 1);
        }
        while (s.size() > 0 && s.back() == ' ') {
            s.pop_back();
        }
        //去掉中间重复空格
        int ii = 0;
        int count = 0;
        while (ii < s.size()) {
            if (s[ii] == ' ') {
                count++;
            }
            if (s[ii] != ' ' && count != 0) {
                s.replace(ii - count, count, " ");
                ii = ii - count + 1;
                count = 0;
            }
            ii++;
        }
        return s;
    }
};