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

➣ Reading Time: 8 minutes

題目出處

139. Word Break

難度

medium

個人範例程式碼

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

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

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

        # end of recursion
        if start > len(s):
            return False
        if start == len(s):
            return True

        # define and split
        ans = False
        for idx in range(start, len(s)):
            prefix = s[start:idx+1] # start to idx
            if prefix in word_dict:
                ans = ans or self.dfs(s, idx+1, word_dict) 
            else:
                continue

        # Memoization search
        self.memo[start] = ans        
        return ans

算法說明

這題可以先嘗試寫一個基本的版本,能夠通過大部分的 case,但是會 TLE

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

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

        return self.dfs(s, 0, wordDict)

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

        # end of recursion
        if start > len(s):
            return False
        if start == len(s):
            return True

        # define and split
        ans = False
        for idx in range(start, len(s)):
            prefix = s[start:idx+1] # start to idx
            if prefix in word_dict:
                ans = ans or self.dfs(s, idx+1, word_dict) 
            else:
                continue

        return ans

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

記憶化搜索 memoization 加速

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

因此我們用一個 memo 紀錄一下,「從 start 開始往後」的結果,在之前的判斷中,答案為 True or False

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

input handling

當沒有 s 時,return False

Boundary conditions

搜尋至 start > len(s) 時,超過結果,為 False
搜尋至 start len(s) 時,剛好結束,為 True

Reference

Howard Weng
Howard Weng

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

文章: 693

1 則留言

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