面试题58：翻转字符串

1 题目描述

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

2 输入

string str

3 输出

string str

4 样例输入

“I am a student.”

5 样例输出

“student. a am I”

6 求解思路

  两次翻转字符串，第一次翻转整个串，第二次翻转子串。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include "MyUtils.h"
using namespace std;

void Reverse(string &str, int begin, int end){
    if(str.length() < 1 || begin == end)
        return ;

    while(begin < end){
        char temp = str[end];
        str[end] = str[begin];
        str[begin] = temp;
        begin++;
        end--;
    }
}

string ReverseSentence(string str){
    int length = str.length();
    if(length < 1)
        return str;
    int begin = 0;
    int end = length - 1;
    // 先翻转整个串
    Reverse(str, begin, end);
    // 再分别翻转里面的串
    begin = 0;
    end = 0;
    while(begin < length){
        if(str[end] == ' ' || end == length){
            Reverse(str, begin, end - 1);
            end++;
            begin = end;
        }
        else
            end++;
    }
    return str;
}

int main()
{
    string str = "I am a student.";
    cout<<ReverseSentence(str);
    return 0;
}