題目出處

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

• 单词拆分（一） · Word Break