题目

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

思路1

• 假如题目要求我们翻转字符串，那么我们可以从末尾往前开始遍历每一个字符，同时将每一个字符添加到临时空间，最后输出临时空间的数据就完成翻转了，这就是倒叙遍历字符串，即从最末尾开始遍历。但是这一题又有些不同，题目要求是以单词为单位进行翻转字符串，所以我们使用双指针来找到一个完整的单词，剩下的步骤基本和上面的一样了，将单词按顺序存到临时的空间，最后输出即可。

代码

class Solution {
    public String reverseWords(String s) {
        // 先去除首位空格
        s = s.trim();
        StringBuilder sb = new StringBuilder();

        int begin = s.length() - 1;
        int end = s.length() - 1;
        while (end >= 0) {
            // 查找第一个空格
            while (begin >= 0 && s.charAt(begin) != ' ') {
                begin--;
            }
            // 找到空格后添加单词，同时手动添加空格
            sb.append(s.substring(begin+1, end+1) + " ");
            // 查找下一个单词的开始
            while (begin >= 0 && s.charAt(begin) == ' ') {
                begin--;
            }
            // 设置下一个单词的结束部分
            end = begin;
        }
        // 由于末尾多了个空格，需要删除
        s = sb.toString().trim();

        return s;
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，遍历一次字符串花费的时间是 N
• 空间复杂度：\(O(N)\)，临时存储字符串所用的空间