58 - I. 翻转单词顺序【双指针】

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"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

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

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

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

2. 标签

• 字符串

• 双指针

3. 解法 - 双指针

这一题类似于翻转域名，如把 www.baidu.com 变成 com.baidu.com ，是一个解题思路。

3.1 Java

class Solution {
    public String reverseWords(String s) {
        // 首先，先去除字符串头尾的空格
        s = s.trim();

        // 倒序遍历字符串，记录当前遍历单词的左右边界 left 和 right
        int left = s.length() - 1;
        int right = s.length() - 1;

        // 结果字符串
        StringBuilder ans = new StringBuilder();

        // 从头到尾，倒序遍历字符串
        while (left >= 0) {
            // 搜索第一个空格
            while(left >= 0 && s.charAt(left) != ' ')
                left--;

            // 找到空格之后，把单词加入到结果字符串中
            String word = s.substring(left + 1, right + 1) + " ";// 这里要记得加空格
            ans.append(word);

            // 跳过单词之间的空格（可能有多个）
            while(left >= 0 && s.charAt(left) == ' ')
                left--;
            
            // right 继续指向下一个单词的尾部
            right = left;
        }
        // 添加单词时会引入多余的空格，记得去除
        return ans.toString().trim();
    }
}

3.2 Kotlin

class Solution {
    fun reverseWords(s: String): String {
        var s = s
        // 首先，先去除字符串头尾的空格
        s = s.trim { it <= ' ' }

        // 倒序遍历字符串，记录当前遍历单词的左右边界 left 和 right
        var left = s.length - 1
        var right = s.length - 1

        // 结果字符串
        val ans = StringBuilder()

        // 从头到尾，倒序遍历字符串
        while (left >= 0) {
            // 搜索第一个空格
            while (left >= 0 && s[left] != ' ')
                left--

            // 找到空格之后，把单词加入到结果字符串中
            val word = s.substring(left + 1, right + 1) + " "
            ans.append(word)

            // 跳过单词之间的空格（可能有多个）
            while (left >= 0 && s[left] == ' ')
                left--

            // right 继续指向下一个单词的尾部
            right = left
        }
        // 添加单词时会引入多余的空格，记得去除
        return ans.toString().trim { it <= ' ' }
    }
}

3.3 复杂度分析

• 时间复杂度 O(N) ：其中 N 为字符串的长度，需要对字符串进行遍历。

• 空间复杂度 O(N) ：结果字符串占用了 O(N) 大小的额外存储空间。

4. 参考

• https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/

• https://leetcode-cn.com/problems/fan-zhuan-dan-ci-shun-xu-lcof/solution/mian-shi-ti-58-i-fan-zhuan-dan-ci-shun-xu-shuang-z/