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

题目：

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"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"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

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

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

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

思路一：

逆序双指针

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)

思路二：

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

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)