151.翻转字符串里的单词

力扣题目链接(opens new window)

这个题的解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

这个题的难点是去除多余的空格，下面我将详细讲解一下去除多余空格的几种方法。

第一种方法是逐个字符的去遍历，遇到多余空格就删除。

class removespace1{
public:
    void removeExtraSpaces(string& s){
        // 删除中间多余空格
        for(int i = s.size() - 1; i > 0; --i){
            if(s[i] == s[i-1] && s[i] == ' '){
                s.erase(s.begin() + i);
            }
        }
        
        // 删除末尾空格
        if(s.size() > 0 && s[s.size() - 1] == ' '){
            s.erase(s.begin() + s.size() - 1);
        }
        // 删除开头空格
        if(s.size() > 0 && s[0] == ' '){
            s.erase(s.begin());
        }
    }
};

这个算法思路很简单，遇到空格就erase。

但是erase操作上套了一个for循环，所以时间复杂度为O(n²)

如果使用双指针去移除空格，最后resize一下字符串的大小，就可以做到时间复杂度为O(n)

void removeExtraspaces(string & s){
        // 1. 双指针删除多余空格
        int slow = 0, fast = 0;  // 快慢指针
        while(s.size() > 0 && fast < s.size() && s[fast] == ' '){
            fast++;  // 去除开头空格
        }
        for(; fast < s.size(); fast++){
            if(fast - 1 > 0 && s[fast - 1] == s[fast] && s[fast] == ' '){
                continue;  // 去除中间多余空格
            }else{
                s[slow++] = s[fast];  // 保留一个空格
            }
        }
        if(slow - 1 > 0 && s[slow - 1] == ' '){
            s.resize(slow - 1);  // 去除末尾空格
        }else{
            s.resize(slow); // 保留末尾空格
        }
    }

双指针的实现过程需要纸上手写画一下，实现过程也相对简单。

这个题还可以联系上27.移除元素，逻辑是一样的只不过是去除空格。

class remove2{
public:
    void removeExtraSpaces(string& s){
        //去除所有空格并在相邻单词之间添加空格, 快慢指针。
        int slow = 0, fast = 0;
        for(int i = 0; i < s.size(); ++i){
            if(s[i] == ' '){ // 遇到非空格就处理，即删除所有空格
                if(slow != 0) {
                    s[slow++] = ' '; // 手动控制空格，给单词之间添加空格，slow ！= 0 说明不是第一个单词，需要在单词前添加空格
                }
                while(i < s.size() && s[i] == ' '){  //补上该单词，遇到空格说明单词结束
                    s[slow++] = s[i++];
                }

            }
        }
        s.resize(slow); // 删除多余空格
    }
};