139. Word Break

📘 題目敘述

給定一個字串 s 與一個字典 wordDict（一組字串），請判斷 s 是否能被切分成一個或多個「字典中的單字」所組成。

注意：字典中的單字可以被重複使用。

條件限制

1 ≤ s.length ≤ 300
1 ≤ wordDict.length ≤ 1000
1 ≤ wordDict[i].length ≤ 20
s 與 wordDict[i] 只包含小寫英文字母
wordDict 中的字串皆不重複

🧠 解題思路（一）：正確但結果TLE

這題我寫得比較像「手動回溯（backtracking）」：

我會把「目前切到 s 的哪個位置」記起來
並且在每個位置上，嘗試用 wordDict 的每個單字去匹配看看
只要有一條路能一路切到 s 的結尾，就回傳 true
如果某個位置把字典都試完了還不行，就回到上一層（pop），改試下一個單字
如果整個 stack 都空了，代表所有可能都試過仍無法組成 s，回傳 false

所有變數

n：wordDict 的大小（字典總共有幾個單字）
num：我用兩條 vector 當成「stack」來記錄回溯狀態
- num[0][k]：第 k 層目前要嘗試的字典索引（我現在試到 wordDict 的第幾個）
- num[1][k]：第 k 層對應的 s 位置（目前切分到 s 的哪個 index）
pos：這一層要從 s[pos] 開始比對
i：這一層要嘗試的字典單字索引（也就是 wordDict[i]）
len：wordDict[i] 的長度
check：這個單字是否能在 s[pos..] 成功匹配

🪜 主要流程步驟

步驟一：初始化 stack

num[0].push_back(0);
num[1].push_back(0);

一開始表示「從 s 的 pos = 0 開始切」，並且從字典的第 0 個單字開始嘗試。

步驟二：只要 stack 還沒空就繼續嘗試

while (!num[0].empty()) { ... }

stack 不空代表「還有路可以走、還有狀態可以回溯」，stack 空代表「所有可能都試完了」，回傳 false。

步驟三：取出目前最上層（最後一層）的狀態

int m = num[0].size() - 1;
int i = num[0][m];
int pos = num[1][m];

這代表目前這一層在做：我現在在 s 的位置 pos，我打算用 wordDict[i] 來試著匹配 s[pos..]。

情況一：這一層的字典都試完了（要回溯）

if (i >= n) {
    num[0].pop_back();
    num[1].pop_back();
    if (!num[0].empty()) {
        num[0].back()++;
    }
    continue;
}

i >= n 表示：這個 pos 下，wordDict 全部都試過了仍不行，所以我把這層狀態 pop 掉（回到上一層），回到上一層後要改試下一個單字。

情況二：嘗試用 `wordDict[i]` 去比對 `s[pos..]`

我先做兩件事：

長度是否超界（如果 pos + len > s.size() 一定不可能匹配）
逐字元比對是否相同，只要有一個字元不同就失敗

最後用 check 表示「這個單字是否能放在這個 pos」。

情況三：匹配成功（往下一層走）

if (check) {
    int npos = pos + len;
    if (npos == s.size()) {
        return true;
    }
    num[0].push_back(0);
    num[1].push_back(npos);
}

如果成功，代表我可以把切分位置推進到 npos = pos + len，若 npos == s.size() 代表剛好切到結尾，直接 true。否則就進入下一層。

情況四：匹配失敗（同一層改試下一個單字）

else {
    num[0][m]++;
}

代表在同一個 pos 上，wordDict[i] 不合，所以我把 i 往後移，改試下一個字典單字。

迴圈結束後（stack 空了）

當 num[0] 變成空，代表所有路徑都嘗試過，每條路都走不到 s 的結尾，因此回傳 false。

💻 程式碼實作

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<vector<int>> num(2); // num[0][k]=位置, num[1][k]=長度
        num[0].push_back(0);
        num[1].push_back(0);
        int n = wordDict.size();
        while (!num[0].empty()) {
            int m = num[0].size() - 1;
            int i = num[0][m];
            int pos = num[1][m];
            if (i >= n) {
                num[0].pop_back();
                num[1].pop_back();
                if (!num[0].empty()) {
                    num[0].back()++;
                }
                continue;
            }
            int len = wordDict[i].size();
            bool check = true;
            if (pos + len > s.size()) {
                check = false;
            } else {
                for (int j = 0; j < len; j++) {
                    if (wordDict[i][j] != s[pos + j]) {
                        check = false;
                        break;
                    }
                }
            }
            if (check) {
                int npos = pos + len;
                if (npos == s.size()) {
                    return true;
                }
                num[0].push_back(0);
                num[1].push_back(npos);
            } else {
                num[0][m]++;
            }
        }
        return false;
    }
};

🧠 解題思路（二）：加入剪枝紀錄

在原本的寫法中，我使用回溯方式嘗試所有可能的切分路徑，但在某些情況下，會反覆走到同一個切分位置 pos，並且每次都重新把整個 wordDict 試過一次，導致時間複雜度過高而 TLE。

因此我在後來的版本中，加入了一個剪枝用的記錄陣列來避免重複嘗試。

新增 `bad[pos]`：記錄「一定失敗的起點」

我新增一個陣列：

bad[pos] = 1 表示：
- 從字串位置 pos 出發
- 已經完整嘗試過所有字典單字
- 最後仍然無法切到字串結尾
- 因此這個 pos 是一條「死路」

之後只要再次走到同一個 pos，就可以直接跳過，不再嘗試。

剪枝實際發生的兩個時機

情況一：進入某一層時，發現 `bad[pos] == 1`

代表這個 pos 之前已經被完整驗證過且不可能成功
因此直接將這一層狀態 pop 掉，回到上一層
並讓上一層改試下一個字典單字
避免再次重複嘗試相同的失敗起點

情況二：某個 `pos` 已把整個字典都試完（`i >= n`）

代表以這個 pos 作為起點，所有單字都無法成功切分
我會將 bad[pos] 標記為 1
表示未來任何路徑再走到這個 pos，都可以直接剪枝

為什麼這樣改就不會 TLE？

原本的寫法中：

同一個 pos 可能在不同路徑下被反覆嘗試
每次都重新從字典第 0 個單字開始試
導致大量重複計算

加入 bad[pos] 之後：

每個 pos 最多只會被「完整嘗試一次」
一旦確認失敗，就不再重複進入
回溯流程仍然保留，但搜尋空間被大幅縮小

因此整體時間複雜度顯著下降，成功避免 TLE。

💻 程式碼實作（剪枝版本）

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<vector<int>> num(2); // num[0][k]=位置, num[1][k]=長度
        num[0].push_back(0);
        num[1].push_back(0);
        int n = wordDict.size();
        vector<int> bad(s.size() + 1, 0);  // bad[pos] = 1 表示從 pos出發已經完整嘗試且不可能成功
        while (!num[0].empty()) {
            int m = num[0].size() - 1;
            int i = num[0][m];
            int pos = num[1][m];
            if (bad[pos]) {
                num[0].pop_back();
                num[1].pop_back();
                if (!num[0].empty()) {
                    num[0].back()++;
                }
                continue;
            }
            if (i >= n) {
                bad[pos] = 1;
                num[0].pop_back();
                num[1].pop_back();
                if (!num[0].empty()) {
                    num[0].back()++;
                }
                continue;
            }
            int len = wordDict[i].size();
            bool check = true;
            if (pos + len > s.size()) {
                check = false;
            } else {
                for (int j = 0; j < len; j++) {
                    if (wordDict[i][j] != s[pos + j]) {
                        check = false;
                        break;
                    }
                }
            }
            if (check) {
                int npos = pos + len;
                if (npos == s.size()) {
                    return true;
                }
                num[0].push_back(0);
                num[1].push_back(npos);
            } else {
                num[0][m]++;
            }
        }
        return false;
    }
};

🔗 題目連結

https://leetcode.com/problems/word-break/