【LeetCode练习题】Reverse Words in a String

Reverse Words in a String

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

反转string里面的单词顺序。

注意在Clarification里头：

一个单词中不包含空格，字符串开始和结尾可以有若干个空格符号，单词与单词之间的空格可以有一个或多个空格符号，我们需要把他变成一个空格。

解题思路：

我是这样想的，把s中的每一个单词都分割出来存储到一个vector里面去，再让这个vector从后往前遍历，result字符串就是题目中要求的格式了，然后赋值给s就行了。

首先，如何去掉字符串s首尾的空格呢？

通过string的find_first_not_of()和find_last_not_of()方法，分别用begin和end指向第一个单词的开始和最后一个单词的结尾处，接下来，只需要在begin和end范围里进行for循环就行了。

那~怎么判断我当前的 i 是在单词里面还是在单词外面呢？

设置一个bool 变量 betweenWord，当betweenWord为true表示在单词内部，betweenWord为false时在单词外面。

当从单词内部到下一个空格字符时，通过substr获得第一个单词，然后设置betweenWord为false，当下一个字符不是空格时候，说明进入了单词内部了，用cur指向该单词的第一个位置，然后继续遍历直到下一个空格处，说明不在单词内部了，我们获得另一个sub单词，存进vector。

最后，用result字符串保存符合格式的字符串，再赋值给s。

代码如下：

class Solution {
public:
    void reverseWords(string &s) {
        size_t begin = s.find_first_not_of(" ");
        if(begin == string::npos){
            //s中全都是空格符号
            s = "";
            return ;
        }
        size_t end = s.find_last_not_of(" ");
        bool betweenWord = true;
        string sub,result;
        size_t cur = begin;
        vector<string> vec;

        for(int i = begin; i <= end; i++){
            if(betweenWord){
                if(s[i] == ' ' || i == end){
                    //进入到单词外部
                    if(i == end){
                        sub = s.substr(cur,i-cur+1);
                        vec.push_back(sub);
                    }
                    else{
                        sub = s.substr(cur,i-cur);
                        vec.push_back(sub);
                    }
                    betweenWord = false;
                }
            }
            else{
                if(s[i] != ' '){
                    //进入单词内部
                    if(i == end){
                        //最后一个单词只有一个字符的情况
                        sub = s.substr(i,1);
                        vec.push_back(sub);
                    }
                    cur = i;
                    betweenWord = true;
                }
            }                    
        }
        
        for(int i = vec.size()-1; i > 0; i--){
            result += vec[i] + " ";
        }
        result += vec[0];
        
        s = result;
    }
};

哎，我写了那么多，别人用十几行就搞定了，这就是差距啊……

Orz……

    void reverseWords(string &s)
    {
        string rs;
        for (int i = s.length()-1; i >= 0; )
        {
            while (i >= 0 && s[i] == ' ') i--;
            if (i < 0) break;
            if (!rs.empty()) rs.push_back(' ');
            string t;
            while (i >= 0 && s[i] != ' ') t.push_back(s[i--]);
            reverse(t.begin(), t.end());
            rs.append(t);
        }
        s = rs;
    }