翻转单词顺序列

爱被打了一巴掌 2022-05-17 06:05 179阅读 0赞

#### 写在前面 ####

> 剑指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就地反转字符串，第一次将字符串整个反转一遍，第二次将每个单词反转一次。