JZ73 翻转单词序列

描述

牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“nowcoder. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a nowcoder.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

数据范围：\1≤n≤100 进阶：空间复杂度 O(n) ，时间复杂度 O(n) ，保证没有只包含空格的字符串

示例1

输入："nowcoder. a am I"
返回值："I am a nowcoder."

解法：两次反转

• 第一次直接反转确定单词位置
• 第二次遍历反转，恢复单词

public class Solution {
    public String ReverseSentence(String str) {
        // 1、第一次反转
        String firstStr = new StringBuilder(str).reverse().toString();

        // 2、定义返回结果,list 用来存放中间结果，res 用来返回
        StringBuilder list = new StringBuilder();
        StringBuilder res = new StringBuilder();

        // 3、遍历firstStr
        for (int i = 0; i < firstStr.length(); i++) {
            // 3.1如果遇到空格
            if (firstStr.charAt(i) == ' ') {
                // 把list中的元素追加到res中
                res.append(list.reverse().toString());
                // 在当前单词后面添加一个空格
                res.append(" ");

                // 清空list中间结果
                list = new StringBuilder();

            }
            // 3.2 没有空格，把元素放入中间缓存区
            else {
                list.append(firstStr.charAt(i));
            }
        }

        // 4、添加最后一个单词
        res.append(list.reverse().toString());
        return res.toString();
    }
}

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)