leetcode：151. 颠倒字符串中的单词

题目来源

• leetcode：151. 颠倒字符串中的单词

题目描述

题目解析

进阶要求（原地 解法）

不能使用辅助空间之后，那么只能在原字符串上下功夫了。

思路：源字符串为："the sky is blue "

• 移除多余空格：“the sky is blue”
• 字符串反转：“eulb si yks eht”
• 单词反转：“blue is sky the”
  

class Solution {
    
public:
    //反转字符串
    void reverse(string& s,int start,int end){
    
        while(start<end){
    
            swap(s[start++],s[end--]);
        }
    }
    //移除多余空格，利用快慢指针
    void removeExtraSpaces(string&s){
    
        int slow=0,fast=0;
        //移除开始位置的空格
        while(s[fast]==' '){
    
            fast++;
        }
        //移除中间位置多余的空格
        while(fast<s.size()){
    
            if(fast>0 && s[fast]==' ' &&s[fast-1]==' '){
    
                fast++;
            }
            else{
    
                s[slow]=s[fast];
                slow++;
                fast++;
            }
        }
        //如果末尾仅有一个空格，则上述无法将该空格移除；如果末尾有很多空格，则上述将保留一个空格，也不符合要求；所以最终可能的情况有二：末尾有一个空格/末尾无空格
        
        if(slow-1>0 && s[slow-1]==' '){
    
            slow--;
        }
        s.resize(slow);
    }
        
    string reverseWords(string s) {
    
        //step1.移除多余空格
        removeExtraSpaces(s);
        //step2.反转整个字符串
        reverse(s,0,s.size()-1);
        //step3.依次反转每个单词
        int start=0;
        for(int i=0;i<s.size();i++){
    
            if(s[i]==' '){
    
                reverse(s,start,i-1);
                start=i+1;
            }
            if(i==s.size()-1){
    
                reverse(s,start,i);
            }
        }
        return s;
    }
}

API

class Solution {
    
public:
    string reverseWords(string s) {
    
        istringstream sin(s);
        string ans, word;
        while(sin>>word){
    
            ans = " " + word + ans;
        }
        return ans.substr(1, ans.size()-1);
    }
};

一次遍历（辅助空间）

class Solution {
    
public:
    string reverseWords(string s) {
    
        if(s.empty()){
    
            return "";
        }

        int L = 0, R = s.size() - 1;
        std::string ans;
        while (L <= R){
    
            while (L <= R && s[L] == ' '){
    
                L++;
            }
            int start = L;
            while (L <= R && s[L] != ' '){
    
                L++;
            }
            int len = L - start;  // 'a '
            if(len != 0){
    
                std::string tmp = s.substr(start, len);
                ans = ans.empty() ? tmp : tmp + " " + ans;
            }
        }
        return ans;
    }
};