翻转单词顺序列

写在前面

剑指offer： 翻转单词顺序列

题目要求

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

解法

方案1：

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.size();
        if(n<=1) return str;
        string res,temp;
        for(int i=0;i<n;++i) {
            if(str[i]==' ') {
                if(res.size())
                    res = temp + ' ' + res;
                else res = temp;
                temp.clear();
            }
            else {
                temp.push_back(str[i]);
            }
        }
        if(res.size()) res = temp + ' ' + res;
        else res = temp;
        if(res.size()<n) return str;
        else return res;
    }
};

分析：我的思路是使用一个temp保存当前得到的单词，当当前的是元素是字符就push_back到temp当中，当当前的元素是空格就将temp添加到res前面：res = temp + ’ ’ + res。最后还需要注意特殊的输入，输入为空，或者输入全为空格的情况。

时间复杂度为O(n) 空间复杂度为o(n)。由于使用新的string保存反转过程当中的中间结果所以有了额外的空间开销。

方案2：
采用就地反转的方式，不使用额外的空间。

class Solution {
public:
    string ReverseSentence(string str) {
        int n = str.size();
        if(n<=1) return str;
        reverse(str,0,n-1);
        int l = 0,r = 0;
        while(l<n) {
            if(str[l]==' ') {
                ++l;
                ++r;
            }
            else {
                while(str[r]!=' '&&r<n)//防止越界操作
                    ++r;
                reverse(str,l,r-1);
                l = r+1;
                r = l;
            }
        }
        return str;
    }

    void reverse(string& str,int l,int r) {
        if(r-l<=0) return;
        while(l<r) {
            char temp = str[l];
            str[l] = str[r];
            str[r] = temp;
            ++l;
            --r;
        }
    }
};

分析：使用reverse就地反转字符串，第一次将字符串整个反转一遍，第二次将每个单词反转一次。