剑指 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)