140. Word Break II

──────────────────────────────────────────────────────────────────────

140. Word Break II

跟 139 一樣是用字典裡的單字拼出 s，但這次不是回答「拼不拼得出來」，而是要把所有拼法都列出來，每一種用空白把單字隔開。

請先參考 139. Word Break

思路

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

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

解題方向

直接從 139 的寫法改過來

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

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

拿掉不需要的回傳值

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

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

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

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)$ ，這題不行。