提醒：本文已翻新

本文已於 2026-06-23 翻新，原文可見 🔗 LeetCode 🔴 140. Word Break II (Old)

🔗 🔴 140. Word Break II

Problem Statement

題目簡述

給定一個字串 s 和一個字串陣列 wordDict，請在 s 中加入空格，使得每個切出的單字都出現在字典中。
返回所有可能的句子，答案可以用任意順序輸出。

注意

句子中可能會包含多個相同的單字。

Constraints

約束條件

$1 \le \text{s.length} \le 20$
$1 \le \text{wordDict.length} \le 1000$
$1 \le \text{wordDict}[i].\text{length} \le 10$
s 和 wordDict[i] 皆由小寫英文字母組成

Example

Input 1

1	s = "catsanddog", wordDict = ["cat", "cats", "and", "sand", "dog"]

Output 1

1	["cats and dog", "cat sand dog"]

解釋

catsanddog 可以切成 cats / and / dog，也可以切成 cat / sand / dog，兩種切法中的每個單字都存在於字典中。

思路：劃分型搜尋與方案輸出

這題是 139. Word Break 的方案輸出版本。139 只問「能不能切」，本題要把所有合法切法都列出來，所以不能只保留布林值，必須把每個後綴能形成的句子方案保存下來。

題型模型：劃分型問題

看到「把字串切成若干段，且每段要滿足條件」時，可以先想成劃分型 DP 或 DFS：固定當前位置，枚舉下一段的結尾；如果這一段合法，就遞迴處理剩下的後綴。

由於 $\text{s.length} \le 20$ ，答案最壞可能是指數級，因此要避免在相同後綴上反覆搜索。

方法一：記憶化搜尋 + 雜湊表

最直接的做法是從目前位置開始，枚舉第一個單字的右端點。若目前這一段在字典中，就把它當成句子的第一個單字，後面接上剩餘後綴的所有合法句子。

問題在於，不同前綴切法可能會走到同一個後綴。例如 catsanddog 中，不同路徑可能都需要回答「從某個位置開始，後面能切出哪些句子」。這就是重疊子問題。

關鍵觀察：後綴決定子問題

對於一個固定的起點，後面所有合法切法只和這個起點之後的字串有關，和前面已經怎麼切無關。
因此可以把「某個起點之後的所有切法」記錄下來。之後再次走到同一個起點時，直接取用結果即可。

為了讓單字查詢更快，先把字典轉成雜湊集合。搜尋函數回傳「從目前起點開始的所有單字列表」，當走到字串尾端時，回傳一個空列表作為拼接的基底。最後再把每個單字列表用空格串成句子。

易錯點：終止狀態要能被拼接

走到字串尾端時，回傳的不是空答案，而是「一種空切法」。這樣上一層才能把最後一個合法單字接上去。若直接回傳空陣列，所有方案都會在最後一步被吃掉。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot 2^n)$ 。最壞情況下每個間隔都能切，合法方案數可達 $2^{n-1}$ ，輸出每個方案還需要線性長度。
空間複雜度： $\mathcal{O}(n \cdot 2^n)$ 。記憶化結果與答案都可能保存指數級方案。

方法二：Trie + 回溯剪枝

方法一在每個起點都會枚舉所有結尾，並用雜湊表判斷目前片段是不是字典單字。這已經可以通過，但有一個可以繼續優化的角度：當某個前綴根本不是任何字典單字的前綴時，再往右延伸也不可能變合法。

這正是 Trie 適合處理的情境。把字典中的單字插入 Trie 後，從某個起點往右掃描時，搜尋路徑若不存在，就能立刻停止這條分支；若目前節點是某個單字的結尾，就可以選擇在這裡切一刀，接著從 Trie 根節點重新匹配下一個單字。

Trie 的作用

Trie 不只是用來判斷「某個字串是不是單字」，更重要的是能判斷「目前字串是不是某些單字的前綴」。一旦連前綴都不是，就可以直接剪枝。

這個做法的回溯狀態可以理解成三部分：目前掃到字串中的位置、目前位於 Trie 的哪個節點、已經切好的單字路徑。每次讀入下一個字元後，有兩種可能：

繼續延伸目前單字。
如果目前節點剛好是單字結尾，就把這個單字加入路徑，下一段從 Trie 根節點重新開始。

當掃完整個字串時，只有在剛好回到 Trie 根節點，也就是上一段已經完整切完時，才是一個合法句子。

易錯點：字串尾端必須剛好切完

如果掃到尾端時仍停在 Trie 的中間節點，表示最後一段只是某個單字前綴，不是完整單字，不能加入答案。

複雜度分析

時間複雜度： $\mathcal{O}(S + n \cdot 2^n)$ ，其中 $S$ 是字典中所有單字的總長度。建立 Trie 需要 $\mathcal{O}(S)$ ，輸出所有方案最壞需要 $\mathcal{O}(n \cdot 2^n)$ 。
空間複雜度： $\mathcal{O}(S + n)$ ，不計答案空間。Trie 佔用 $\mathcal{O}(S)$ ，遞迴深度與路徑長度為 $\mathcal{O}(n)$ 。

方法三：狀態壓縮枚舉劃分點

還可以換一個角度：長度為 $n$ 的字串，有 $n-1$ 個相鄰字元間隔，每個間隔只有兩種選擇：切或不切。因此所有切法其實就是這 $n-1$ 個間隔的所有子集。

不妨用一個二進位狀態表示切分點集合。從左到右掃描字串，遇到被選中的間隔，或掃到最後一個字元時，就把目前累積出的片段拿去字典中檢查。只要有任何片段不在字典中，這個狀態就不是合法切法；否則把所有片段用空格連起來，就是一個答案。

為什麼這個方法也合理？

本題 $n \le 20$ ，所以最多只有 $2^{19}$ 種切分點集合。這個數量雖然是指數級，但和答案上界同階，而且寫法能直接對應「枚舉所有可能切法」這件事。

這個做法沒有記憶化，也沒有 Trie 剪枝，優點是模型非常直觀；缺點是會檢查大量最後不合法的切分狀態。它更像是利用資料範圍較小時的一種枚舉方案。

複雜度分析

時間複雜度： $\mathcal{O}(n \cdot 2^n)$ 。共有 $2^{n-1}$ 種切分狀態，每種狀態需要線性掃描字串。
空間複雜度： $\mathcal{O}(n)$ ，不計答案空間。單次枚舉只需要保存目前片段與切分結果。

本題要點

本題訓練的是「劃分型問題如何輸出所有方案」。若只問可行性，可以用布林 DP；若要輸出方案，就要讓狀態保存後綴的所有組合。Trie 則是把「枚舉結尾」中的無效前綴提早剪掉；位元枚舉則是從切分點集合的角度重新理解全部方案。

參考資料

【宫水三叶】运用「二进制枚举」找具体方案

Code

方法一：記憶化搜尋 + 雜湊表

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        wordSet = set(wordDict)

        @cache  # Memoization
        def dfs(i: int) -> List[List[str]]:  # 返回 s[i:] 的所有可能劃分
            if i == n:
                return [[]]  # 劃分完成，返回一個空的劃分結果
            res = []
            for j in range(i, n):  # 枚舉當前單字的結尾位置
                word = s[i : j + 1]
                if word in wordSet:
                    for words in dfs(j + 1):
                        res.append([word] + words)
            return res

        return [" ".join(words) for words in dfs(0)]  # 將劃分的結果轉為字串

方法二：Trie + 回溯剪枝

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        root = TrieNode()  # Trie
        for word in wordDict:
            node = root
            for ch in word:
                c = ord(ch) - ord("a")
                if node.children[c] is None:
                    node.children[c] = TrieNode()
                node = node.children[c]
            node.isEnd = True  # 標記當前 Trie 節點是某個單字的結尾

        ans = []
        path = []

        def dfs(i: int, node: TrieNode, word: str) -> None:  # Backtracking
            if i == n:
                if node == root:
                    ans.append(" ".join(path))
                return
            c = ord(s[i]) - ord("a")
            if node.children[c] is None:  # 如果當前字元不在 Trie 中，則直接返回 (剪枝)
                return
            word += s[i]  # 當前字元加入 word
            node = node.children[c]

            # 1. 不劃分，繼續往下找
            dfs(i + 1, node, word)

            # 2. 如果當前字元是單字的結尾，可以劃分
            if node.isEnd:
                path.append(word)
                dfs(i + 1, root, "")  # 繼續從 Trie 的根節點開始
                path.pop()

        dfs(0, root, "")
        return ans

方法三：狀態壓縮枚舉劃分點

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n = len(s)
        wordSet = set(wordDict)
        ans = []
        for i in range(0, 1 << (n - 1)):  # 枚舉所有劃分點形成的子集合
            path = []  # 劃分結果
            st = 0  # 當前單字的起始位置
            for j in range(n):
                if i & (1 << j) or j == n - 1:  # 在 s[j] 之後要劃分
                    word = s[st : j + 1]  # 當前單字
                    st = j + 1  # 更新下一個單字的起始位置
                    if word not in wordSet:  # 無法劃分
                        break
                    path.append(word)
            else:
                ans.append(" ".join(path))
        return ans

寫在最後

Cover Image Credit

The cover image was created by @たろたろ. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.

標籤很多的題目，相對應的也有很多解法。