每日一题，提升自己。今天分享一道关于翻转单词顺序的题目，且听我细细道来。

字符串 - 翻转单词顺序

1. 题目描述

        输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串 “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. 无空格字符构成一个单词。
2. 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
3. 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

2. 解题思路

2.1 思路一

        还是老套路，遍历字符串。题目说无空格字符构成一个单词，所以在遍历字符串的时候只需要遇到空格则代表一个单词的结束，字符串的前后也会有空格，为了减少无用遍历，在真正遍历之前先去除两端空格。每遍历一个单词就把它加入到返回结果的前面。在返回前去除返回结果两端空格。

2.2 思路二

        本质还是遍历字符串，只不过这个使用的是双指针去进行遍历。还是先将开头和结尾处多余的空格去掉，从后向前遍历，通过前后指针锁定单词，跳过中间空格，最终将整个句子中的单词反转。

复杂度：

• 时间复杂度：O(n)。
• 空间复杂度：O(n)。

3. 算法流程

3.1 思路一流程

1. 初始化返回结果res=""和临时单词变量word=""，先去除两端空格，然后依次遍历字符串中的字符。
2. 如果该字符不是空格，就添加到word里面。
3. 如果该字符是空格，证明至少扫描完一个单词，此时判断档次是否为空，因为存在多个空格的情况。如果不为空则加在返回结果前，中间用空格连接，之后继续遍历。
4. 遍历完字符之后，再次判断单词word是否为空，不为空则加在返回结果前，中间用空格连接。
5. 最后将拼接好的字符串res去除两端空格返回即可。

3.2 思路二流程

1. 首先将原始字符串去掉开头和结尾的空格得到tmp字符串，便于之后直接从单词处理开始。
2. 初始化单词起始位置start=tmp.length-1和单词结尾指针end=tmp.length-1，位置在字符串结尾处。
3. 初始化结果字符串res为空字符串。
4. 当start>=0时说明字符串未遍历结束，作为循环条件。
5. 在tmp[start]位置，如果不为空格，说明还没有获取到完成的单词，start--。
6. 在获取到完成单词之后，截取[start+1,end+1]这一段字符串加入结果字符串中，因为是从后向前扫描单词的，所以可以之际加到res后面，通过空格连接。
7. 在tmp[start]位置，如果为空格，说明还没有到下一个单词结尾，则start--。
8. 到单词结尾位置之后，end=start，往复进行上述流程，将单词全部反转。
9. 最后将结果字符串res去掉两端多余空格返回即可。

4. 代码实现

4.1 思路一代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public static String reverseWords(String str){
    str = str.trim();
    String res = "";
    String word = "";
    for (int i=0;i<str.length();i++){
        char c = str.charAt(i);
        if (c!=' '){
            word += c;
        }else if (!word.equals("")){
            res = word + " " + res;
            word = "";
        }
    }
    if (!word.equals("")){
        res = word + " " + res;
    }
    return res.trim();
}

4.2 思路二代码

Java代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static String reverseWords(String str){
    String tmp = str.trim();
    int start = tmp.length()-1;
    int end = tmp.length()-1;
    String res = "";
    while (start >= 0){
        while (start>=0 && tmp.charAt(start)!=' '){
            start--;
        }
        res += tmp.substring(start+1,end+1) + " ";
        while (start>=0 && tmp.charAt(start)==' '){
            start--;
        }
        end = start;
    }
    return res.trim();
}