LeetCode #151：Reverse Words In A String(颠倒字符串中的单词)

题目描述

本题是使用双指针（快慢指针法）的一道综合性问题。首先通过快慢指针对字符串中多余的空格进行清除，随后要对整个串进行一次反转操作，再要通过快慢指针来界定单词的边界，最后要对串中每一个单词再进行反转。

class Solution {
public:
    string reverseWords(string s) {
        removeExtraSpaces(s); // 使用双指针法去除多余空格
        tranverse(s, 0, s.length() - 1);
        // 使用双指针法截取单词
        int slow = 0;
        int fast = 0;
        for(; fast < s.length(); fast ++) {
            if(s[fast] == ' ') {
                tranverse(s, slow, fast - 1);
                slow = fast + 1;
            }
        }
        tranverse(s, slow, fast - 1);
        
        return s;
    }
    
    // 快指针遇到多余的空格自增，慢指针不动；快指针遇到非多余的空格，将快指针指向的值赋给慢指针，快慢指针同时自增。最终慢指针所在的位置就是去除字符串中间空格后的子串末尾（还需去除末尾的空格）
    void removeExtraSpaces(string& s) {
        int slow = 0, fast = 0; // 定义快指针，慢指针
        while (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 { // if不满足，说明字符串末尾无空格
            s.resize(slow); // 重新设置字符串大小
        }
    }
    
    void tranverse(string& s, int begin, int end) {
        for(;begin < end; begin ++, end --) {
            swap(s[begin], s[end]);
        }
    }
};