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

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

解题思路：字符串

本题主要考察了字符串的一些常用方法

解题流程：

• 去掉字符串两端的空格，使用 _str.trim()_ 方法
• 将字符串按照空格分割为字符串数组，使用 _str.split(" ")_ 方法
• 倒序遍历字符串数组，将每个字符串与 “ “ 添加至 StringBuilder 中；在分割字符串时，如果两个单词之间有多个空格时，分割后的字符数组会出现“空单词”即：(“”)，所以，遍历到空单词时，要跳过
• 最后一个单词后也会有一个 “ “，所以我们也要对最后的字符串做去掉两端空格的处理

代码

class Solution {
    public String reverseWords(String s) {
        String[] split = s.trim().split(" ");
        StringBuilder sb = new StringBuilder();
        for(int i = split.length - 1; i >= 0; i--){
            if(split[i].equals("")){
                continue;
            }
            sb.append(split[i]);
            sb.append(" ");
        }
        return sb.toString().trim();
    }
}

复杂度分析

• 时间复杂度：O(N)

该算法总体的时间复杂度为 O(N)

String 常用方法的时间复杂度如下：

• _split()_ : O(N)
• _trim()_ : O(N)； 最差情况下，当字符串全为空格时，时间复杂度为 O(N)
• _reverse()_ : O(N)
• _join()_ : O(N)

• 空间复杂度：O(N)

将字符串分割成字符串数组占用了 O(N) 的额外空间