代码随想录刷题-字符串-反转字符串里的单词

反转字符串里的单词

本节对应代码随想录中：代码随想录，讲解视频：字符串复杂操作拿捏了！ | LeetCode:151.翻转字符串里的单词_哔哩哔哩_bilibili

习题

题目链接：151. 反转字符串中的单词 - 力扣（LeetCode）

给你一个字符串 s ，请你反转字符串中单词的顺序。

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

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

注意：输入字符串 s 中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 2：
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

我的解法

解决这题，有两个难点。一是要反转字符串里的单词，二是去除多余的空格

对于反转单词，可以先将字符串进行反转，然后再对其中的每个单词再反转，也就实现了反转字符串中单词的顺序。具体来说，遍历字符串，并用一个变量 last 始终记录单词的第一个字符的位置，当遇到空格或者到了字符串的下一个位置的时候将前面的单词用 reverse 函数反转

难点或者说可优化的点在于去除多余的空格。我的解法是 while 循环遍历字符串，当遇到空格的时候再用个 while 循环从当前位置向后找直到遇到非空的字符。这样就确定了一段连续的空格字符串，用 erase 函数删去这段字符串后，还要在开始的位置再插入一个空格充当单词之间的空格

class Solution {
   public:
    // 去除多余空格
    void removeExtraSpaces(string& s) {
        int cur = 0;
        while (cur < s.size()) {
            if (s[cur] == ' ') {
                int tmp = cur;
                while (s[cur] == ' ') {
                    cur++;
                }
                s.erase(tmp, cur - tmp);
                // 删除空格字符串后，cur指针位置也要前移到之前第一个空格的位置
                cur = tmp; 
                if (tmp != 0 && tmp != s.size())
                    s.insert(tmp, 1, ' ');
            }
            cur++;
        }
    }
    string reverseWords(string s) {
        removeExtraSpaces(s);
        // 反转单词
        int last = 0;
        reverse(s.begin(), s.end());
        for (int i = 0; i <= s.size(); i++) {
	        // 字符串最后一个字符不是空格时也要反转
            if (s[i] == ' ' || i == s.size()) {
                reverse(s.begin() + last, s.begin() + i);
                last = i + 1;
            }
        }
        return s;
    }
};

• 时间复杂度：O($n^2$)。其中n为字符串s的长度。主要在removeExtraSpaces函数中，因为erase操作和插入操作的时间复杂度都是O(n)，而循环嵌套的次数也可能是O(n)级别的。而在字符串反转的过程中，应用了STL库函数reverse，时间复杂度是O(n)，所以总体时间复杂度为O(n^2)
• 空间复杂度：O($1$)。并没有使用额外空间来存储数据，只是在原字符串上进行修改，因此空间复杂度为常数级别

双指针

双指针解法反转单词和上面我的解法相同，不过优化了去除空格的过程。上面我的解法是用了两个 while 循环去除空格，而双指针法和数组中的移除元素那题类似。这里相当于移除空格，只不过移除空格后还要手动添加单词间的空格。

用快指针遍历字符串，慢指针重新赋值 s。快指针遍历到不等于空格的时候操作 slow 指针将当前的单词赋值给 s 的合适位置。同样，每次需要手动添加单词间的空格。

我写的时候没想到这种方法，果然操作字符串和数组很多时候都能用双指针进行优化

class Solution {
   public:
    // 整体思想参考https://programmercarl.com/0027.移除元素.html
    // 去除所有空格并在相邻单词之间添加空格, 快慢指针。
    void removeExtraSpaces(string& s) {
        int slow = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != ' ') {
                // 字符串的起始不用加空格
                if (slow != 0)
                    s[slow++] = ' ';
                // 将新的单词赋给s
                while (i < s.size() && s[i] != ' ') {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);  // slow的大小即为去除多余空格后的大小。
    }
    string reverseWords(string s) {
        removeExtraSpaces(s);
        int last = 0;
        reverse(s.begin(), s.end());
        for (int i = 0; i <= s.size(); i++) {
            if (s[i] == ' ' || i == s.size()) {
                reverse(s.begin() + last, s.begin() + i);
                last = i + 1;
            }
        }
        return s;
    }
};

• 时间复杂度：O($n$)。其中n为字符串s的长度。主要在removeExtraSpaces函数中，使用了双指针的方法去除多余空格，时间复杂度是O(n)，在反转单词的过程中使用了STL库函数reverse，时间复杂度也是O(n)，因此总体时间复杂度是O(n)
• 空间复杂度：O($1$)。并没有使用额外空间来存储数据，只是在原字符串上进行修改，因此空间复杂度为常数级别