双指针法-力扣151 反转字符串中的单词

力扣151-反转字符串中的单词
给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：
输入: "the sky is blue"
输出: "blue is sky the"

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

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

提示：
1 <= s.length <= 10^4
s 包含英文大小写字母、数字和空格 ' '
s 中至少存在一个单词

思路

首先剔除字符串中多余的空格，多余的空格存在于字符串开头、末尾以及中间两个或以上连续的空格。开头和末尾的空格直接去除即可，而中间连续空格则需要保留一个。
第二步，将整个字符串反转。如此，实现了各单词整体位置上的反转。
那么最后便是将各单词内部字母反转。

代码实现

在这里我们实现一种时间复杂度为O(n)，空间复杂度为O(1)(原地对字符串进行修改，不额外分配空间)

为实现原地进行修改，我们用到双指针法。
定义快慢指针，快指针赋值为字符串中第一个非空格下标，慢指针为字符串开头。
使用快指针遍历字符串，判断值是否符合要求。符合则将其存入慢指针，同时，慢指针移动
最后判断遍历完成后的字符串尾部是否存在多余空格，若存在则将其去除。并更新字符串长度。

int fast = 0, slow = 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] == ' '){
    continue;
  }else{
    s[slow++] = s[fast];
  }
}
if(s[slow-1] == ' ' && slow -1 >0){
  s.resize(slow-1);
}else{
  s.resize(slow);
}

反转整个字符串，可以自行编写，也可调用库函数，这不是本题的重点所在。

对单词内部字母的反转，只需要考虑好什么时候对哪一部分进行反转。这里我使用一种相似于双指针的方法。快慢指针同时指向字符串开头，快指针对字符串进行遍历。当快指针遍历元素为空格时，对慢指针到快指针-1的元素进行反转，同时慢指针改为指向快指针+1。

for(int start = 0,end = 0; end <= s.size(); end++){
  if(s[end] == ' ' || end == s.size()){
    reserve(s,start,end-1);
    start = end+1;
  }
}

下面是可以在力扣网站中直接提交通过的完整代码

class Solution {
public:
    string reverseWords(string s) {
        int fast = 0, slow = 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] == ' '){
                continue;
            }else{
                s[slow++] = s[fast];
            }
        }
        if(s[slow-1] == ' ' && slow -1 >0){
            s.resize(slow-1);
        }else{
            s.resize(slow);
        }
        reserve(s,0,s.size()-1);
        for(int start = 0,end = 0; end <= s.size(); end++){
            if(s[end] == ' ' || end == s.size()){
                reserve(s,start,end-1);
                start = end+1;
            }
        }
        return s;
    }
private:
    void reserve(string& s,int start,int end){
        for(int i = start, j = end; i < j; i++, j--){
            swap(s[i],s[j]);
        }
    }
};

总结

其实在各种高级语言中有很多功能强大的库函数，我们应该熟悉这些库函数，但是在我们做算法题时应该考虑使用库函数对题目的影响。如果库函数只能解决题目中的一小步，或者你对这个库函数的内部运作原理已经非常熟悉，那么直接调用也无伤大雅。例如题解中的reserve函数是我自行编写的，没有调用库函数，是因为我想要加强一下对反转操作的印象。(我刚在反转字符串以及反转字符串II 两题中使用) 但是reserve函数中我却调用了swap函数进行互换，因为我认为我对swap函数的认识已经足够清晰，同时这也显然不是本题的意图所在。
事实上，如果使用Python，本题仅用几行代码即可解决。另外，在C++中可以使用erase直接删除字符串中元素，但是时间复杂度会有所变化。