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

➣ Reading Time: 9 minutes

題目出處

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

Howard Weng
Howard Weng

我是 Howard Weng,很多人叫我嗡嗡。這個網站放了我的各種筆記。希望這些筆記也能順便幫助到有需要的人們!如果文章有幫助到你的話,歡迎幫我點讚哦!

文章: 728

★留個言吧!內容有誤或想要補充也歡迎與我討論!