首页技术正文

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

工程师殿福技术 2022年11月20日

0 收藏 462 点赞 3,380 浏览 1047 个字

本题题目链接

题目描述

我的题解

方法一：库函数split()

要注意str.split()函数:
- 字符串str前有 n 个空格时，分割出来的字符串列表中会多出 n 个空字符串；
- 字符串str某两个字符串中有 n 个空格，分割出的字符串列表会多 n-1 个空字符串。
- 字符串str最后有空格，分割出的字符串列表里不会多出空字符串

split()的例子如下：

本题代码如下

    public String reverseWords(String s) {
        if (s == null) return s;        String[] strList = s.split(" ");
        StringBuilder res = new StringBuilder();        for (int i = strList.length - 1; i >= 0; i--) {
            if (!"".equals(strList[i])) {
                res.append(strList[i]+" ");
            }
        }
        return res.toString().trim();
    }

复杂度分析：

时间复杂度 O(N) ：各函数时间复杂度如下

split() 方法：为 O(N) ；
trim() 方法：最差情况下（当字符串全为空格时），为 O(N)O(N) ；

空间复杂度 O(N) ：单词列表strList占用线性大小的额外空间。

方法二：双指针

思路分析

声明两个指针 i,j 分别用来确定单词头和单词尾，初始位置均指向字符串尾。倒序遍历字符串：
- 找到单词尾：指针 i一直向左移动，直到 i<0 或指向的字符不再是空格时，停止移动，此时把 i 的值赋给j。此步骤确定了单词尾指针。
- 找到单词头：指针 i 一直向左移动，直到 i<0 或指向的字符串不再是字母时，停止移动，此时，找到了单词头（单词从下标 i+1 开始到 j 结束）。

代码如下

    public String reverseWords(String s) {
        if (s == null) return s;
        StringBuilder res = new StringBuilder();        int j = s.length()-1;
        int i = j;
        while (i >= 0) {
            // 找单词尾
            while (i >= 0 && s.charAt(i) == ' ') i--;
            j = i;
            // 找单词头
            while (i >= 0 && s.charAt(i)!=' ') i--;
            res.append(s.substring(i + 1, j+1)+' '); // 左闭右开
        }
        return res.toString().trim();    }

复杂度分析