题解 | #翻转单词序列#

描述
        牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
示例1
输入：
"nowcoder. a am I"
返回值：
"I am a nowcoder."

方法一：单词切割逆转
核心思想：
        将字符串按照空格进行切分，并保存每一个分割的单词。然后将分割后的单词逆序输出即可。
具体步骤如下：
1）循环分割字符串
2）查找字符串中的空格，查找成功则，截取单词并保存，同时更新字符串
3）查找失败，则说明为最后一个单词，保存单词并退出循环
4）逆序输出保存的单词

图解：

核心代码：

string ReverseSentence(string str) {
    vector<string> v;
    int i,index=0;
    while(1){
        index=str.find(" ");    //查找字符串中的空格
        if(index!=-1){            //找到分割位置
            string s1=str.substr(0,index);   //获取分割的单词串
            v.push_back(s1);
            str=str.substr(index+1);      //更新主字符串
        }
        else{       //最后一个单词
            v.push_back(str);
            break;
        }
    }
    string s="";
    for(i=int(v.size())-1;i>=0;i--){
        if(i!=0){      //除最后一个单词外的其他单词
            s+=v[i];        //单词合并，并以空格隔开
            s+=" ";
        }else{        //最后一个单词
            s+=v[i];
        }
    }
    return s;
}

时间复杂度O(n)
空间复杂度O(n)


方法二：利用istringstream分割字符串
核心思想：
        将字符串输入到istringstream流中，istringstream流会按照空格将字符串进行分割，因此只需要在istringstream流中读取分割后的子字符串保存即可。然后逆序输出保存后的单词。

图解：

核心代码：

string ReverseSentence(string str) {
    vector<string> result;
    istringstream ss(str);   //按照空格分割字符串
    string word;
    while(ss>>word) {   //保存单词
        result.push_back(word);
    }

    string s="";
    for(int i=int(result.size())-1;i>=0;i--){
        if(i!=0){      //除最后一个单词外的其他单词
            s+=result[i];        //单词合并，并以空格隔开
            s+=" ";
        }else{        //最后一个单词
            s+=result[i];
        }
    }
    return s;
}

时间复杂度O(n)
空间复杂度O(n)