(第12天)【leetcode题解】151、反转字符串中的单词

151、反转字符串中的单词

题目描述

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

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

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

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

要求：空间复杂度为O(1)；

思路

去除多余空格:收尾无空格，单词之间只有一个空格

定义快慢指针，快指针负责寻找正确的元素，慢指针负责从头开始给字符串赋值。

反转字符串
反转单个单词

代码

class Solution {
public:
    //原地反转字符串
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++,j--) {
            swap(s[i], s[j]);//交换操作
        }
    }

    //去除多余空格
    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] == ' ' && s[fastIndex - 1] == 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, 0, s.size() - 1);//原地反转所有字符
        //开始逐个反转单词
        int start = 0;//指向每一个单词的开头
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') {//到达空格或字符串尾部，说明一个单词结束，进行反转
                reverse(s, start, i - 1);
                start = i + 1;//把start指向下一个单词的开头
            }
        }
        return s;
    }
};

优化【去除多余空格函数】之后的代码：

class Solution {
public:
    //原地反转字符串
    void reverse(string& s, int start, int end) {
        for (int i = start, j = end; i < j; i++,j--) {
            swap(s[i], s[j]);//交换操作
        }
    }

    //去除空格
    void removeExtraSpaces(string& s) {
        int slow = 0;//慢指针辅助赋值操作
        for (int i = 0; i < s.size();i++) {
            if (s[i] != ' ') {//如果目前遍历到的字符不是空格，就进行处理
                if (slow != 0) s[slow++] = ' ';//给每个单词之间添加空格
                while (i < s.size() && s[i] != ' ') {
                    s[slow++] = s[i++];
                }
            }
        }
        s.resize(slow);//slow的大小就是删除多余空格后字符串的大小
}

    //反转字符串中的单词
    string reverseWords(string s) {
        removeExtraSpaces(s);//去除多余空格
        reverse(s, 0, s.size() - 1);//原地反转所有字符
        //开始逐个反转单词
        int start = 0;//指向每一个单词的开头
        for (int i = 0; i <= s.size(); ++i) {
            if (i == s.size() || s[i] == ' ') {//到达空格或字符串尾部，说明一个单词结束，进行反转
                reverse(s, start, i - 1);
                start = i + 1;//把start指向下一个单词的开头
            }
        }
        return s;
    }
};