剑指Offer58-I翻转单词顺序，你能做到吗？

本文共计1633个文字，预计阅读时间需要7分钟。

剑指 Offer 58- I. 翻转单词顺序/题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如，输入I am a。

结果：a am I

剑指 Offer 58 - I. 翻转单词顺序

</br></br>

题目：

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

示例1：

输入: "the sky is blue" 输出: "blue is sky the"

示例2：

输入: " hello world! " 输出: "world! hello" 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例3：

输入: "a good example" 输出: "example good a" 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。

• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

</br></br>

思路一：

逆序双指针

1.用n记录当前字符串长度，再开辟一个新的字符串str用来存放逆序遍历到的单词；

2.逆序遍历，当字符不为空格时，使用right记录下当前i的位置，然后i--向前查找下一个空格，当s[i] == ' '时，可以通过right - i得到当前单词的长度，i + 1得到单词的首字母，通过substr函数将该单词放到新的字符串str中；

3.当我们逆序遍历完成之后，得到新的字符串，此时str已经是原来字符串翻转后形成的，但是要注意的是，使用str += s.substr(i + 1, right - i) + " "向str中追加最后一个单词时，空格也被放到了里面，所以要单独对最后一个空格进行处理；

• 可以使用substr函数进行处理即return str.substr(0,str.size() - 1)；

• 也可以使用erase函数删除最后一个空格，但是此时要判断str是否为空字符串，避免erase时数组越界；

• 还可以使用pop_back函数直接尾删掉最后一个字符。

我们以字符串we are family为例，头部两个空格，are和family中间三个空格，尾部三个空格。具体过程可参考下图：

代码如下：

class Solution { public: string reverseWords(string s) { int n = s.size(); string str;//string类默认值为空 //从结尾开始向前遍历，这样的话不用翻转，单词顺序直接就是翻转后的 for(int i = n - 1; i >= 0; i--) { //当s[i]不为空时，追加到新字符串 if(s[i] != ' ') { int right = i;//记录此时i的位置 while( i >= 0 && s[i] != ' ' ) //要注意这里条件的先后顺序 { i--; } //right - i 计算的是字符长度 //s[i]此时为空格，i+1就是单词的首个字符 str += s.substr(i + 1, right - i) + " "; } } //最后这里的str字符串最后一个元素为空格 // 1. return str.substr(0,str.size() - 1); //3. str.pop_back(); // return str; //2. if(str == "") //还要考虑当字符串为空的情况 return str; str.erase(str.size() - 1, 1); return str; } };

时间复杂度：O(N)

空间复杂度：O(N)

</br></br>

思路二：

通过三个指针对原子符串进行修改从而实现翻转单词顺序。

1.先将整个字符串翻转；

2.设置一个变量idx用来将单词从头开始填入字符串，设置变量start从头开始找，当s[start] != ' '时，说明此时为单词的头部，向后遍历，当s[end] != ' '时找到单词结尾，通过reverse(s.begin() + idx - (end -start), s.begin() + idx);对单词进行翻转；

3.start = end;更新start，并找下一个单词……当idx != 0时说明已经插入了单词需要添加空格s[idx++] = ' '；

4.当字符串中单词找完，即循环结束之后，s.erase(s.begin() + idx,s.end());删除idx开始的往后的字符，因为原字符串中的单词已经通过循环放到了前面。

我们以字符串we are family为例，头部两个空格，are和family中间三个空格，尾部三个空格。具体过程可参考下图：

代码如下：

class Solution { public: string reverseWords(string s) { //直接翻转整个字符串 reverse(s.begin(),s.end()); int n = s.size(); int idx = 0; //用来记录单词和给空格 for(int start = 0; start < n; start++) { //当s[start]不等于空格时记录单词 if(s[start] != ' ') { //当idx不等于0时，说明此时字符串已经完成了一个单词的写入，所以要加上空格 if(idx != 0) s[idx++] = ' '; //开始向后遍历，找到单词的结尾 int end = start; while(end < n && s[end] != ' ') s[idx++] = s[end++]; //单词写入之后对这个单词进行翻转 reverse(s.begin() + idx - (end -start), s.begin() + idx); //再更新start,找下一个单词 start = end; } } //将从idx开始的往后的字符全部删除 s.erase(s.begin() + idx,s.end()); return s; } };

时间复杂度：O(N)

空间复杂度：O(1)