力扣 – 劍指 Offer 58 – I. 翻轉單詞順序

• 2021 年 11 月 2 日
• 筆記
• 倒序遍歷, 雙指針, 字元串, 演算法

題目

劍指 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)\)，臨時存儲字元串所用的空間