題目描述:給定一個字串 s,將其中的單詞順序反轉後回傳。單詞之間以一個或多個空格分隔,結果中單詞之間只保留一個空格,且不含前後多餘的空格。
解題思路:本題有兩種主要做法:
方法一:利用 istringstream 分割(簡潔版)
用 istringstream 將字串以空白為分隔符切割成單詞列表,可自動處理連續空格。將所有單詞存入 vector<string>,再從後往前遍歷,用空格拼接,即得到反轉後的結果。
方法二:原地操作(進階版,不使用額外字串空間)
ABCDE → EDCBA,此時單詞的相對位置已反轉,但每個單詞的字元是倒序的。方法一代碼更簡潔易懂,面試中兩者都是常見解法,方法二展示了原地字串操作的技巧。
時間複雜度:O(n) — istringstream 掃描整個字串一次為 O(n),反向拼接也是 O(n),整體線性時間,其中 n 為字串長度。
空間複雜度:O(n) — 需要 vector<string> 儲存所有單詞,以及結果字串,總空間與輸入字串長度成正比。原地做法可降至 O(1) 額外空間(不計輸出)。
1. Use istringstream to parse s, extracting words one by one (auto-skips whitespace). 2. Push each word into a vector. 3. Initialize result as empty string. 4. Iterate vector from last index to 0: a. If result is non-empty, append a space. b. Append words[i] to result. 5. Return result. [In-place alternative] 1. Reverse the entire string. 2. Scan left to right; for each word found: a. Copy word characters to the write pointer position. b. Reverse the just-copied word in place. c. Append one space after the word. 3. Remove the trailing space. 4. Return the trimmed substring.
方法一:istringstream 分割 + 反向拼接(本題主解法)
利用 C++ istringstream 的 >> 運算子自動跳過連續空白,將單詞存入 vector 後從後往前拼接。時間 O(n),空間 O(n),程式碼最簡潔,適合面試快速實作。
方法二:原地雙重 reverse(Two-Pointer In-place) 先 reverse 整個字串,再逐一 reverse 每個單詞,同時用雙指標壓縮多餘空格。時間 O(n),額外空間 O(1)(只需常數個指標)。適合面試官要求「不使用額外空間」的場景,但實作細節較多,容易出現邊界錯誤。
方法三:手動分割 + stack 手動掃描字串,將每個單詞壓入 stack,再逐一彈出拼接。思路與方法一相同,但用 stack 代替 vector 的反向遍歷,語義更直觀。時間 O(n),空間 O(n),與方法一差異不大。
char[])形式給出,而非 std::string,解法是否有所不同?istringstream 和 reverse 是否還能正確處理?應如何修改?