[剑指Offer] 44.翻转单词顺序列

题目描述

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

【思路】先把由空格分割的每个字符串翻转，最后翻转整个字符串。

 1 class Solution
 2 {
 3 public:
 4     string ReverseSentence(string str)
 5     {
 6         int len = str.length();
 7         int num = 0;
 8         int pos[len];
 9         memset(pos, 0, sizeof(pos));
10         //得到所有空格的位置，多个连续空格也可以
11         for(int i = 0; i < len; i ++)
12         {
13             if(str[i] == ' ')
14                 pos[num++] = i;
15         }
16         if(num == 0) return str;
17         if(num == 1)
18         {
19             reverse(str.begin(),str.begin() + pos[0]);
20             reverse(str.begin() + pos[0] + 1,str.end());
21             reverse(str.begin(),str.end());
22             return str;
23         }
24         for(int i = 0; i < num; i ++)
25         {
26             if(i == 0)              //翻转第一个空格前面的字符串
27                 reverse(str.begin(),str.begin() + pos[i]);
28             else if(i == num - 1)   //翻转最后一个空格之后的字符串
29                 reverse(str.begin() + pos[i] + 1,str.end());
30             else                    //翻转两空格之间的字符串
31                 reverse(str.begin() + pos[i - 1] + 1,str.begin() + pos[i]);
32         }
33         reverse(str.begin(),str.end());
34         return str;
35     }
36 };