151. Reverse Words in a String

📘 題目敘述

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

單字之間以一個或多個空白 ' ' 分隔
回傳的結果中，單字之間只保留一個空白
不可以在結果字串的開頭或結尾出現多餘的空白

條件限制

1 ≤ s.length ≤ 10^4
s 可能包含英文字母、數字與空白
至少包含一個單字

🧠 解題思路

這題我沒有直接用 stringstream 或內建切割工具，而是選擇自己掃描字串，記錄每個單字的起始位置，再「倒著組合答案」。

我的核心想法是：

先找出每個「單字開始的位置」
再從最後一個單字開始，依序把單字接到結果字串
中間自行控制空白的數量，避免多餘空白

所有變數

words：紀錄每一個單字「起始索引」的陣列
n：字串 s 的長度
check：是否準備遇到一個新單字
- true：前一個是空白，下一個非空白會是新單字
- false：目前仍在同一個單字中
rev：最後要回傳的反轉後字串
m：單字總數
pos：用來往後掃描單字內容的指標

🪜 主要流程說明

第一階段：找出每個單字的起始位置

我先從左到右掃描整個字串：

若遇到空白 ' '：
- 表示目前不是單字內容
- 將 check 設為 true
若遇到非空白，且 check == true：
- 代表這是一個「新單字的開頭」
- 把該位置的索引存進 words
- 並將 check 設為 false

這樣可以確保：

連續空白只會記錄一次
每個單字只會被記錄「起始位置」

第二階段：由後往前組合單字

words 中存的是單字的起始位置，而且是由左到右的順序。

因此我從最後一個單字開始處理：

令 pos = words[k]
從該位置開始，一直往右讀字元
直到遇到空白或字串結尾為止
將這段單字加進 rev

這樣就能達到「反轉單字順序」的效果。

空白的處理方式

if (k > 0) {
    rev += " ";
}

只有在「後面還有單字」時才補一個空白，這樣可以確保單字之間只有一個空白，結尾不會多出空白。

整體邏輯總結

這份程式的邏輯可以簡化成三件事：

掃描字串，記錄每個單字的起點
從最後一個單字開始，逐個取出並接到結果
手動控制空白，避免多餘空白出現

這樣的寫法雖然比較低階，但可以完整掌控字串的行為，也有助於理解「字串掃描」與「狀態控制」的技巧。

💻 程式碼實作

class Solution {
public:
    string reverseWords(string s) {
        vector<int> words;
        int n = s.size();
        bool check = true;
        string rev;
        for (int i = 0; i < n; i++) {
            if (s[i] == ' ') {
                check = true;
            } else if (s[i] != ' ' && check) {
                check = false;
                words.push_back(i);
            }
        }
        int m = words.size();
        int pos = n - 1;
        for (int k = m - 1; k >= 0; k--) {
            pos = words[k];
            while (pos < n && s[pos] != ' ') {
                rev += s[pos];
                pos += 1;
            }
            if (k > 0) {
                rev += " ";
            }
        }
        return rev;
    }
};

🔗 題目連結

https://leetcode.com/problems/reverse-words-in-a-string/