題目出處

140. Word Break II

難度

hard

個人範例程式碼

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        if not s:
            return []

        self.memo = {}
        return self.dfs(s, wordDict)

    def dfs(self, s, word_dict):
        if s in self.memo:
            return self.memo[s]

        # end of recursion
        if len(s) == 0:
            return []

        # define and split
        partitions = []

        # full match
        if s in word_dict:
            partitions.append(s)

        # part match
        for idx in range(0, len(s)):
            prefix = s[:idx+1] # 0 to idx
            # print(prefix)
            if prefix not in word_dict:
                continue

            sub_partitions = self.dfs(s[idx+1:], word_dict) # start from idx+1
            for partition in sub_partitions:
                partitions.append(prefix + " " + partition)

        self.memo[s] = partitions
        return partitions

算法說明

• 此題的前一題，只需要判斷可不可行就好，可參考：

【Leetcode】python – [139] Word Break 個人解法筆記

這題可以先嘗試寫一個基本的版本，用 dfs 搜索出全部的結果，
這題很佛心不會 TLE，但真的很慢XDDD

思考方式為用一個 start 作為 pointer，切出「到目前為止之前的全部內容」

以下的方法基本沒有太大問題，只是速度比較慢而已，此時我們可以用記憶化搜索的方式加速

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        if not s:
            return False

        self.ans = []
        self.dfs(s, 0, wordDict, [])
        return self.ans

    def dfs(self, s, start, word_dict, prefix_words):

        # end of recursion
        if start > len(s):
            return
        if start == len(s):
            self.ans.append(" ".join(prefix_words))
            return 

        # define and split
        for idx in range(start, len(s)):
            prefix = s[start:idx+1] # start to idx
            if prefix in word_dict:
                prefix_words.append(prefix)
                self.dfs(s, idx+1, word_dict, prefix_words)
                prefix_words.pop() # backtracking
            else:
                continue
        return 

最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解

記憶化搜索 memoization 加速

加速的思路，是來自我們思考每次在遞迴的過程中，
最終都會有一段處理相同文字的過程。
(可以想像，每次的開頭不同時，結尾我們都在反覆處理一樣的東西)

因此我們用一個 memo 紀錄一下，紀錄「相同的文字」，我們上次處理的結果

因此我們這邊判斷 s 是否有存在於 memo 中，有則直接 return partition 結果

input handling

當沒有 s 時，return []

Boundary conditions

搜尋至 start = len(s) 時，剛好抵達結束搜尋的範圍 (其他狀況應該是無法抵達的)

Reference

• 单词拆分II · Word Break II