LeetCode剑指offer58-1翻转单词顺序[

本文正在参加「Java主题月 - Java 刷题打卡」，详情查看 活动链接

题目描述

翻转单词顺序

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

说明：

​ 无空格字符构成一个单词。
​ 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
​ 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

思路分析

首先看到该算法题，因为句子中的单词是有空格间隔开的，很多人会想到使用spilt()，然后将分割后的单词一个个拼接，思路也比较简单。但是这肯定不是面试官想看到的解法，因为使用了spilt()大大简化了本题的解决过程。但是本文也将提供该种解法。该解法的时间复杂度是

O(n)，空间复杂度也是

O(n)。

还有一种解法是使用双指针解法，从尾部向前开始遍历，当碰到空格时，使用subString()截取值，然后继续遍历。这里为什么可以使用subString()呢，因为这只是一个提取字符串的函数，并没有大大简化核心代码流程，只是起到一个辅助的作用，所以在做这类题目是也要了解出题人的意图。该解法的时间复杂度是

O(n)，空间复杂度也是

O(n)。

代码展示

解法一：使用 StringBuilder 进行拼接，使用spilt()对字符串进行分割，大大简化解题过程，该解法面试时忌用，时间复杂度是

O(n)，空间复杂度也是

O(n)。

    public String reverseWords(String s){ //该方法面试忌用
            String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
            StringBuilder res = new StringBuilder();
            for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
                if(strs[i].equals("")) continue; // 遇到空单词则跳过
                res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
            }
            return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
    }
复制代码

解法二：使用双指针解法，当碰到空格时，使用subString()截取值，然后继续遍历。时间复杂度是

O(n)，空间复杂度也是

O(n)。

    public String reverseWords(String s) {
        String temp = s.trim();
        int j = temp.length() - 1;
        int i = j;
        StringBuilder sb = new StringBuilder();
        while (i >= 0) {

            while (i >= 0 && temp.charAt(i) != ' ') {
                i--;
            }
            sb.append(temp.substring(i + 1, j + 1));
            while (i >= 0 && temp.charAt(i) == ' ') {
                i--;
                j = i;
            }
            sb.append(" ");

        }
        return sb.toString().trim();
    }
复制代码

总结

了解常用的 Java API 当然很重要，但是如果在解题是某个 API 方法将题目大大简化，这时候我们就应该留意是否应该使用它了，API 应该是一种辅助作用（作用有限），双指针的解法在反转类题目非常有用。