151. Reverse Words in a String

題目 / Problem

中文： 給定一個字串 s，將字串中的單字順序反轉。

• 一個單字定義為連續的非空白字元。
• 原字串中的單字之間至少有一個空白字元分隔。
• 回傳一個新字串，其中單字以反向順序排列，且彼此之間僅用一個空白分隔。
• 注意：s 可能包含前導空白、尾隨空白，或多個空白；回傳結果不能有多餘的空白。

English: Given a string s, reverse the order of the words.

• A word is a maximal sequence of non-space characters.
• Words in s are separated by at least one space.
• Return a string of the words in reverse order, joined by a single space.
• The input may contain leading/trailing spaces and multiple spaces between words; the output must contain none of these.

Constraints: - 1 <= s.length <= 10^4 - s contains English letters (upper- and lower-case), digits, and spaces. - There is at least one word in s.

Example:

Input:  "  hello world  "
Output: "world hello"

名詞解釋 / Glossary

• Two pointers / 雙指針：用兩個索引變數同時掃描字串，一個記錄單字的開頭、一個記錄結尾。常用來在一次遍歷中切出多個區段。A technique that uses two indices to walk through a string/array — here, one marks the start of a word, the other its end.
• In-place / 原地修改：直接在原本的記憶體上修改資料，不另外配置一個等大的陣列。Modifying data directly in the existing buffer instead of allocating a new array of equal size.
• Reverse trick / 三次反轉技巧：先反轉整個字串，再反轉每個單字。這樣字母順序在每個單字內被「修正回正向」，但單字之間的順序卻變成原本的相反。Reverse the whole string, then reverse each word individually — net effect: word order is flipped, but each word reads forward again.
• malloc / free：C 語言中動態配置與釋放堆積（heap）記憶體的函式。LeetCode 的 C 題目通常要求回傳的字串用 malloc 配置。C functions for allocating and freeing heap memory; LeetCode's C runtime expects the returned string to be malloc-ed.
• std::string / std::stringstream：C++ 標準函式庫的字串類別與「字串流」，可以像讀取 cin 一樣從字串中以空白為分隔讀出 token。C++ standard string and string-stream classes; the stream reads whitespace-delimited tokens from a string just like cin does from input.
• std::vector<T>：C++ 的動態陣列，可自動擴充容量。A dynamic array in C++ that grows as you push elements onto it.

思路

最直觀的做法是：先把字串依照空白切成單字陣列，反轉這個陣列，再用單一空白接起來。這在 C++ 裡用 stringstream 幾乎一行就能寫完，時間是 O(n)、額外空間也是 O(n)（單字陣列本身）。對於初學者，這通常是最容易理解、最不容易出錯的版本，所以 C++ 的解法就採用它。但題目的 Follow-up 問「若字串可變動，能否在 O(1) 額外空間就地完成？」這就要用「三次反轉」的技巧：第一步，把整個字串先反轉一次（"the sky is blue" → "eulb si yks eht"）；第二步，從左到右掃描，每遇到一個單字就把那個單字內部再反轉一次（"eulb" → "blue"），這樣每個單字內部回到正向，但單字之間的順序已經和原本相反；第三步，處理多餘空白——用一個「寫入指標」覆寫原陣列，遇到單字才寫入，並且只在單字之間補一個空白。整個過程只需要常數額外變數，符合 in-place 的要求。為什麼三次反轉行得通？因為反轉是個可逆操作：兩次反轉抵消，所以只反轉「外層」（整串）但讓「內層」（每個單字）也跟著反轉一次，最後外層的順序變動才會「留下來」。

The brute-force idea is: split the string by spaces into a list of words, reverse the list, and join with a single space. In C++ this fits in a few lines using stringstream, runs in O(n) time, and uses O(n) extra space for the word list — perfectly fine and the easiest version to read, so that's what the C++ solution does. The follow-up, however, asks for O(1) extra space when the string is mutable, which is the natural setting for C (where s is a char* we can rewrite). The technique is three reversals: (1) reverse the entire string, so "the sky is blue" becomes "eulb si yks eht"; (2) walk left-to-right and reverse each individual word, restoring the letters inside each word to forward order while leaving the word order reversed; (3) compact the result by writing it back into the same buffer with exactly one space between words and no leading/trailing space. This works because reversal is its own inverse: reversing twice cancels out, so we reverse the outer sequence (the whole string, which flips word order) and then "undo" it only inside each word, leaving the word-order flip as the net effect. The compaction step handles arbitrary runs of spaces in one pass using a write index.

逐步走查 / Walkthrough

以輸入 s = "the sky is blue"（長度 15）走過 C 解法。 Tracing the C solution on s = "the sky is blue" (length 15).

Step 1 — Reverse the whole buffer / 反轉整個字串：

Step 2 — Walk through and reverse each word / 逐一反轉每個單字：

Step 3 — Compact spaces / 壓縮多餘空白：

此例本來就只有單一空白，所以寫入指標 w 從頭走到尾後，內容不變：blue is sky the。最後在 s[w] 寫入 '\0' 結束字串。 In this example there were no extra spaces to begin with, so the write pointer w walks through and writes back the same characters, terminating with '\0'. The final string is "blue is sky the".

（若輸入是 " hello world "，第 3 步會跳過開頭兩個空白、保留 hello、寫入單一空白、保留 world、跳過尾部兩個空白，結果為 "world hello"。） (If the input were " hello world ", Step 3 would skip the leading two spaces, keep hello, write one space, keep world, and skip the trailing two spaces, yielding "world hello".)

Solution — C

// 演算法：三次反轉 + 原地壓縮空白。
// Algorithm: three reversals + in-place space compaction.
// (1) 反轉整個字串 / reverse the whole buffer.
// (2) 反轉每個單字 / reverse each word individually.
// (3) 用寫入指標重新排版，去除多餘空白 / use a write pointer to remove extra spaces.

#include <string.h>   // strlen — 取得字串長度 / get string length

// 反轉 s[l..r]（含兩端）的字元 / Reverse characters of s[l..r] inclusive.
static void reverseRange(char *s, int l, int r) {
    while (l < r) {                      // 當左指針還在右指針左邊 / while left is still left of right
        char t = s[l];                   // 暫存左邊字元 / stash the left character
        s[l] = s[r];                     // 把右邊搬到左邊 / move right char into left slot
        s[r] = t;                        // 再把暫存的放到右邊 / place the stashed char into right slot
        l++;                             // 左指針往右走一格 / advance left
        r--;                             // 右指針往左走一格 / retreat right
    }
}

// LeetCode 要求的函式簽名 / LeetCode-required signature.
// 回傳的字串可以是原 buffer（原地修改）/ returned string may be the same buffer (in-place).
char* reverseWords(char* s) {
    int n = (int)strlen(s);              // n = 字串長度 / length of s

    // Step 1：反轉整個字串 / reverse the entire buffer.
    reverseRange(s, 0, n - 1);           // 把 s[0..n-1] 整段反轉 / flip the whole range

    // Step 2：逐一反轉每個單字 / reverse every word in place.
    int i = 0;                           // 掃描指標 / scanning index
    while (i < n) {
        while (i < n && s[i] == ' ') i++; // 跳過空白 / skip spaces between words
        int j = i;                       // j 指向單字開頭 / j marks the word's start
        while (j < n && s[j] != ' ') j++; // 把 j 推到單字結尾後一格 / push j just past the word
        if (i < j) {                     // 若真的找到了一個單字 / if a word was found
            reverseRange(s, i, j - 1);   // 反轉 s[i..j-1]（單字本身）/ reverse this word
        }
        i = j;                           // 從單字之後繼續掃描 / continue after the word
    }

    // Step 3：壓縮多餘空白，重寫回 s / compact spaces by rewriting s in place.
    int w = 0;                           // w = 下一個寫入位置 / next write slot
    int r = 0;                           // r = 讀取位置 / read position
    int wroteWord = 0;                   // 是否已經寫過至少一個單字 / have we written any word yet
    while (r < n) {
        if (s[r] != ' ') {               // 讀到非空白：屬於某個單字 / non-space: part of a word
            if (wroteWord) {             // 不是第一個單字 → 先補一個空白 / not first word → add separator
                s[w++] = ' ';            // 寫入分隔空白 / write the single space
            }
            while (r < n && s[r] != ' ') { // 把整個單字搬過去 / copy the whole word
                s[w++] = s[r++];         // 一個字元一個字元複製 / character by character
            }
            wroteWord = 1;               // 標記已寫過單字 / mark that we've emitted a word
        } else {
            r++;                         // 是空白：直接略過 / it's a space: skip it
        }
    }
    s[w] = '';                         // C 字串結尾符號 / NUL-terminate the C string

    return s;                            // 回傳同一塊 buffer / return the same buffer (in-place)
}

Solution — C++

// 演算法：用 stringstream 以空白為分隔讀出每個單字到 vector，
// 然後從後往前接起來，中間補一個空白。O(n) 時間，O(n) 額外空間。
// Algorithm: use a stringstream to tokenize on whitespace into a vector,
// then concatenate from back to front with single-space separators.
// O(n) time, O(n) extra space.

#include <string>     // std::string
#include <sstream>    // std::istringstream — 讓我們像讀 cin 一樣從字串讀出 token
#include <vector>     // std::vector — 動態陣列 / dynamic array

class Solution {
public:
    std::string reverseWords(std::string s) {
        std::istringstream iss(s);         // 把 s 包成「字串流」/ wrap s as an input stream
        std::vector<std::string> words;    // 存放每個單字 / will hold each parsed word
        std::string word;                  // 暫存當前讀到的單字 / buffer for the current token

        // operator>> 會自動跳過任何空白並讀出下一個非空白 token，
        // 所以多重空白、前導/尾隨空白都會被自動忽略。
        // operator>> automatically skips any whitespace and extracts the next
        // non-space token — extra/leading/trailing spaces are handled for free.
        while (iss >> word) {              // 持續讀直到沒有 token / loop until no token left
            words.push_back(word);         // 把這個單字放進 vector 尾端 / append to vector
        }

        std::string result;                // 最終答案字串 / output string
        result.reserve(s.size());          // 預先配置空間，避免多次重新配置 / reserve to avoid reallocs

        // 從最後一個單字往前走 / iterate from the last word back to the first.
        // (int) 轉型是為了讓 i 可以變成 -1 而不會繞回去（size_t 是無號的）。
        // The (int) cast lets i go to -1 safely; size_t is unsigned and would wrap.
        for (int i = (int)words.size() - 1; i >= 0; --i) {
            result += words[i];            // 接上這個單字 / append the word
            if (i > 0) {                   // 若不是最後一次（即還有後續單字要接）/ if more words follow
                result += ' ';             // 補一個分隔空白 / add a single-space separator
            }
        }

        return result;                     // 回傳組合好的結果 / return the assembled string
    }
};

複雜度 / Complexity

• Time: O(n) — n 是字串長度。C 版本做了三趟掃描（整體反轉、逐字反轉、壓縮空白），每趟都是線性。C++ 版本的 stringstream 讀取也是線性，最後一次拼接同樣線性。n is the length of s. The C version makes three linear passes (reverse all, reverse each word, compact). The C++ version's stream tokenization and final concatenation are also linear.
• Space: C 版本 O(1)，C++ 版本 O(n) — C 版本直接在原 buffer 上覆寫，只用了幾個整數變數。C++ 版本用了 vector<string> 儲存所有單字，加上輸出字串，因此是 O(n)。 The C solution rewrites the input buffer in place using only a handful of integer variables. The C++ solution stores all words in a vector<string> plus builds an output string, so it's O(n).

Pitfalls & Edge Cases

• Leading / trailing spaces / 前導與尾隨空白：直接反轉整個字串會把尾部空白帶到前面，所以一定要有壓縮步驟。Naively reversing the buffer brings trailing spaces to the front; the compaction pass is what removes them.
• Multiple spaces between words / 單字間多重空白：壓縮時要用「遇到單字才補空白」的邏輯（用 wroteWord 旗標），而不是「遇到空白就寫一個空白」。Compact by adding a separator before each word after the first, not by copying every space — otherwise runs of spaces become runs of single spaces, which is still wrong.
• Single-word input / 只有一個單字：例如 "hello"。三次反轉後仍是 "hello"，壓縮步驟也正確輸出單一單字、不加多餘空白。For "hello", three reversals leave it as "hello", and the compaction step emits no trailing space because the separator is only added before subsequent words.
• All-spaces input is excluded / 全為空白的輸入被排除：題目保證至少有一個單字，所以不必處理「結果為空」的情況；若不放心，最後的 wroteWord 旗標自然會讓輸出為空字串。The problem guarantees at least one word, but the wroteWord flag would correctly produce an empty result anyway.
• size_t underflow in C++ / C++ 中的 size_t 下溢：words.size() 是無號型別，若直接寫 for (size_t i = words.size() - 1; i >= 0; --i)，當 i 變 0 後再 -- 會繞回極大值造成無窮迴圈。解法用 (int) 轉型避開。Looping with an unsigned index toward 0 is a classic infinite-loop bug — casting to int (safe here, since n <= 10^4) sidesteps it.
• Forgetting the NUL terminator in C / C 解法忘記補 '\0'：壓縮後字串可能比原本短，若不寫入 s[w] = '\0'，回傳的 C 字串會帶著舊資料的尾巴。After compaction the string may be shorter than the original; without s[w] = '\0' the returned C string would still show the old tail bytes.