題目出處
難度
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
算法說明
- 此題的前一題,只需要判斷可不可行就好,可參考:
這題可以先嘗試寫一個基本的版本,用 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) 時,剛好抵達結束搜尋的範圍 (其他狀況應該是無法抵達的)