---
title: "140. Word Break II"
url: "https://laigary.com/interview/coding/140-word-break-ii"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-08-03"
tags: ["Backtrack", "Dynamic Programming", "Classic"]
---

# 140. Word Break II

[140. Word Break II](https://leetcode.com/problems/word-break-ii/)

跟 [139](/interview/coding/139-word-break) 一樣是用字典裡的單字拼出 `s`，但這次不是回答「拼不拼得出來」，而是要**把所有拼法都列出來**，每一種用空白把單字隔開。

請先參考 [139. Word Break](/interview/coding/139-word-break)

## 思路

在 [139. Word Break](/interview/coding/139-word-break) 中，只要判斷是否可以找到組合就好，但是在這個進階題目中，不只是要找到是否有這個組合，還進一步問，如果存在著不同的排列組合，要進一步提供出所有的組合。

而要找排列組合的話，回溯法就會是最好的方法，可以直接修改前一題自頂向下的作法並改成回溯法的方式來做，因為是要找到所有的排列組合，所以會需要遍歷所有的情況，這時候就不需要使用記憶法來記錄子問題。

## 解題方向

### 直接從 139 的寫法改過來

差別只有兩個：多帶一個 `candidate` 記路徑，走到底時把它接成句子收進答案。

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        wordDict = set(wordDict)

        ans = []
        def dfs(i, candidate):
            if i == len(s):
                ans.append(" ".join(candidate))
                return True
            res = False
            for word in wordDict:
                if len(s) - i >= len(word):
                    if s.startswith(word):
                        candidate.append(word)
                        if dfs(i + len(word), candidate):
                            res = True
                        candidate.pop()
                        
            return res
        dfs(0, [])
        return ans
```

### 拿掉不需要的回傳值

另外判斷是否有找到目標的條件判斷也並不需要了，因此可以簡化成以下方式。

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        wordDict = set(wordDict)

        ans = []
        def dfs(i, candidate):
            if i == len(s):
                ans.append(" ".join(candidate))
                return
            for word in wordDict:
                if len(s) - i >= len(word):
                    if s.startswith(word):
                        candidate.append(word)
                        dfs(i + len(word), candidate)
                        candidate.pop()

        dfs(0, [])
        return ans
```

其實傳指針的方法，不需要真的做越位檢查，字串匹配的時候已經把越位的情況給排出了

```python
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        
        res = []

        def backtrack(curr, i):
            if i == len(s):
                res.append(" ".join(curr))
                return
            
            for word in wordDict:
                if s[i:].startswith(word):
                    curr.append(word)
                    backtrack(curr, i + len(word))
                    curr.pop()
        
        backtrack([], 0)

        return res
```

## 補充

### 為什麼這題不用記憶化

139 用 `@cache` 是因為 `dfs(i)` 的答案只是一個布林值，重算沒有意義。這題的 `dfs(i)` 要產生的是「從 `i` 開始的**所有句子**」—— 就算記下來，最後還是得把每一句都吐出來，省不掉輸出本身的成本。

而且 LeetCode 保證 `len(s) <= 20`，直接窮舉完全跑得動。**時間是被「答案有幾個」決定的，不是被「重複的子問題」決定的** —— 極端一點的測資（`s = "a" * 20`、字典裡有 `"a"` 到 `"aaaaaaaaaa"`）實測會產生 **521472 個答案**。

## 複雜度

設 $n$ 是 `s` 的長度、$m$ 是單字數、$L$ 是最長的單字長度。

- 時間 $O(2^n \times n)$ — 每個位置都可以是切點或不是，最多 $2^{n-1}$ 種拼法；每找到一種還要 $O(n)$ 把單字接成句子。搜尋過程本身另外是 $O(n \times m \times L)$
- 空間 $O(n)$ — 遞迴深度加上 `candidate`，回傳的答案不計入

這題的指數是**逃不掉的** —— 答案本身就可能有指數多個，跟 139 只回傳一個布林值完全不同，所以 139 能用記憶化壓到 $O(n \times m \times L)$，這題不行。