題目描述

給定一個字符串，逐個翻轉(zhuǎn)字符串中的每個單詞。
說明：無空格字符構(gòu)成一個單詞。輸入字符串可以在前面或后面包含多余的空格，但是反轉(zhuǎn)后的字符不能包括。如果兩個單詞間有多余的空格，將反轉(zhuǎn)后單詞間的空格減少到只含一個。

數(shù)據(jù)結(jié)構(gòu)

• 數(shù)組+雙指針、雙端隊列、字符串

算法思維

• 遍歷、逆序、字符串操作

解題要點

• 熟練使用 Java 語言的 String 字符串特性
• 了解 trim() / split() / join() / substring() 等函數(shù)的底層原理
• 妥善使用 String 特性函數(shù)，高效實現(xiàn)功能

解題步驟

一. Comprehend 理解題意

解法一：把單詞看成整體，翻轉(zhuǎn)單詞的順序

1. 把字符串按空格切割，得到多個單詞
2. 翻轉(zhuǎn)單詞順序，拼接成新的字符串
3. 處理多余空格

解法二：先翻轉(zhuǎn)字符串，再翻轉(zhuǎn)字母順序

1. 翻轉(zhuǎn)整個字符串，單詞的順序正確了
2. 翻轉(zhuǎn)單詞的每個字母
3. 處理多余空格

解法三：雙端隊列解法

1. 向雙端隊列頭部依次存入每個單詞
2. 從雙端隊列頭部依次取出每個單詞

二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法

解法一：翻轉(zhuǎn)每個單詞的順序

• 數(shù)據(jù)結(jié)構(gòu)：數(shù)組 / 棧 / 雙端隊列
• 算法思維：遍歷、逆序

解法二：翻轉(zhuǎn)單詞的字母

• 數(shù)據(jù)結(jié)構(gòu)：數(shù)組
• 算法思維：遍歷、雙指針

解法三：雙端隊列

• 數(shù)據(jù)結(jié)構(gòu)：雙端隊列
• 算法思維：遍歷、后進先出

三. Code 編碼實現(xiàn)基本解法

解法一：Java 語言特性 實現(xiàn)

1. 將字符串按空格切割成單詞數(shù)組
2. 翻轉(zhuǎn)單詞順序
   使用數(shù)組工具類轉(zhuǎn)成集合
   使用集合工具類進行翻轉(zhuǎn)
3. 重新將單詞與空格拼接成新字符串
   使用String類的靜態(tài)方法join進行拼接

class Solution {
    public String reverseWords01(String s) {

        if (s == null || "".equals(s = s.trim()))
            return "";

        //細(xì)節(jié)；正則匹配多個空格
        // 1.將字符串按空格切割成單詞數(shù)組
        String[] strings = s.split("\\s+");

        // 2.翻轉(zhuǎn)單詞順序。細(xì)節(jié)：數(shù)組、集合工具類的使用
        List<String> list = Arrays.asList(strings);
        Collections.reverse(list);

        // 3.重新將單詞與空格拼接成字符串
        return String.join(" ", list);

    }
}

時間復(fù)雜度：O(n)
? ? 切割過程進行遍歷查找：O(n)
? ? 翻轉(zhuǎn)與拼接：O(n) + O(n)

空間復(fù)雜度：O(n)
? ? 切割使用了 2個數(shù)組：O(n)
? ? join 使用了 1個數(shù)組：O(n)

執(zhí)行耗時：7 ms，擊敗了 46.81% 的Java用戶
內(nèi)存消耗：39.3 MB，擊敗了 20.75% 的Java用戶

解法二：數(shù)組+雙指針 實現(xiàn)

1. 按字符串長度定義新數(shù)組，臨時存儲
2. 倒序遍歷字符串，定位單詞起止索引
3. 讀取單詞起止索引范圍內(nèi)的字符，寫入新數(shù)組
4. 還原指針，用以定位下個單詞
5. 將新數(shù)組中合法數(shù)據(jù)生成新字符串

邊界問題

• 以字符串中的空格為單詞分界
• 字符串首尾的空格應(yīng)跳過

細(xì)節(jié)問題

• 倒序遍歷時，先定義單詞尾指針
• 讀取到下一個空格，索引+1定位單詞開始指針
• 注意單詞間的多個空格，只保留一個

class Solution {
    public String reverseWords(String s) {

        int len;

        if (s == null || (len = s.length()) == 0)
            return "";

        // 1.準(zhǔn)備工作：初始化新數(shù)組，定義單詞起止索引
        char[] chars = new char[len]; //新字符數(shù)組
        int first = -1, last = -1, index = 0; //單詞起止索引
        
        // 2.倒序遍歷字符串，定位單詞起止索引
        for (int i = len - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (c != ' ') { //非空格：第一個非空格為單詞結(jié)尾字符
                if (last == -1) last = i; // 2.1.定位last
                if (i == 0) first = i; //細(xì)節(jié)：處理字符串首字符不是空格
            } else { //空格：以“空格+1”為單詞開始索引
                if (last != -1) first = i + 1; // 2.2.定位first
            }
            
            // 3.讀取單詞起止索引范圍內(nèi)的字符，寫入新數(shù)組
            if (first >= 0 && last >= 0 ) {
                //細(xì)節(jié)：如果新數(shù)組中已經(jīng)有數(shù)據(jù)，先存放一個空格，再放數(shù)據(jù)
                if (index > 0) chars[index++] = ' ';
                while (first <= last) {
                    chars[index++] = s.charAt(first);
                    first++;
                }
                first = last = -1; // 4.還原指針，用以定位下個單詞
            }
        }

        return String.valueOf(chars, 0, index); // 5.將新數(shù)組中合法數(shù)據(jù)生成新字符串返回
    }
}

時間復(fù)雜度：O(n)
? ? 倒序遍歷字符串：O(n)
? ? 讀取所有單詞：O(n)

空間復(fù)雜度：O(n)
? ? 需要一個臨時數(shù)組：O(n)
? ? 兩個指針：O(1)
? ? 最后重新生成一個數(shù)組：O(n)

執(zhí)行耗時：3 ms，擊敗了 75.57% 的Java用戶
內(nèi)存消耗：39.1 MB，擊敗了 43.42% 的Java用戶

解法三：雙端隊列 解法思路

1. 往雙端隊列頭部依次存入每個單詞
   ? 以空格為單詞分界，將單詞字符存入緩沖區(qū)
   ? 從緩沖區(qū)取出單詞存入雙端隊列頭部
   ? 注意過濾掉首尾、單詞間多余空格
2. 從雙端隊列頭部依次取出每個單詞
   ? 使用join方法，將空格拼接到每個單詞之間
   ? 注意不要遺漏最后一個單詞

class Solution{
    public String reverseWords(String s) {
        int left = 0, right = s.length() - 1;
        Deque<String> d = new ArrayDeque<String>();
        StringBuilder word = new StringBuilder();
        while (left <= right) {
            char c = s.charAt(left);
            if (c != ' ') {
                word.append(c);
            } else {
                if (word.length() != 0) {
                    // 將單詞 push 到隊列的頭部
                    d.offerFirst(word.toString());
                    word.setLength(0);
                } 
            }
            ++left;
        }
        if (word.length() > 0) d.offerFirst(word.toString());
        return String.join(" ", d);
    }
}

時間復(fù)雜度：O(n)
? ? 遍歷字符串：O(n)
? ? 讀取所有單詞：O(n)
? ? 雙端隊列擴容：O(n)

空間復(fù)雜度：O(n)
? ? 需要一個雙端隊列：O(n)
? ? 一個字符串緩沖區(qū)：O(n)
? ? 最后重新生成一個數(shù)組：O(n)

執(zhí)行耗時：7 ms，擊敗了 46.81% 的Java用戶
內(nèi)存消耗：38.7 MB，擊敗了 93.19% 的Java用戶

四. Consider 思考更優(yōu)解

剔除無效代碼或優(yōu)化空間消耗

• 新建數(shù)組的容量不確定，用字符串長度比較浪費空間，是否有緩沖區(qū)可以使用？
• 數(shù)據(jù)結(jié)構(gòu)（棧、雙端隊列）的使用是必要的嗎？

尋找更好的算法思維

• 使用語言特性：切割 + 反向遍歷
• 參考其它算法

五. Code 編碼實現(xiàn)最優(yōu)解

最優(yōu)解：切割+反向遍歷

1. 將字符串按空格進行切割
   ? 按單個字符 " " 切割，降低處理復(fù)雜度
   ? 切割結(jié)果是一個字符串?dāng)?shù)組，可能包含 " "
2. 反向遍歷數(shù)組中的每個單詞
3. 將每個單詞存入字符串緩沖區(qū)中
   ? 存入前加空格作為前綴
   ? 遍歷完成后進行截取

class Solution {
    public String reverseWords(String s) {
        if (s == null || "".equals(s = s.trim()))
            return "";
        // 按空格進行切割，而不是 \s+
        String[] strs = s.split(" ");
        StringBuilder sb = new StringBuilder();
        // 反向遍歷
        for (int i = strs.length - 1; i >= 0; i--) {
            if (strs[i].length() != 0)
                // 拼接單詞前加一個空格
                sb.append(" ").append(strs[i]);
        }
        // 截掉第一個空格
        return sb.substring(1);
    }
}

時間復(fù)雜度：O(n)
? ? 生成數(shù)組過程遍歷字符串：O(n)
? ? 讀取所有單詞：O(n)

空間復(fù)雜度：O(n)
? ? 生成一個數(shù)組：O(n)
? ? 一個字符串緩沖區(qū)：O(n)
? ? 最后重新生成一個數(shù)組：O(n)

執(zhí)行耗時：1 ms，擊敗了 99.99% 的Java用戶
內(nèi)存消耗：38.6 MB，擊敗了 97.51% 的Java用戶

六. Change 變形與延伸

題目變形

• （練習(xí)）自己實現(xiàn)String類的trim、split方法和字符串緩沖區(qū)，實現(xiàn)本題
• （練習(xí)）使用棧翻轉(zhuǎn)單詞