140. Word Break II
💡
請先參考 139. Word Break
在 139. Word Break 中，只要判斷是否可以找到組合就好，但是在這個進階題目中，不只是要找到是否有這個組合，還進一步問，如果存在著不同的排列組合，要進一步提供出所有的組合。
而要找排列組合的話，回溯法就會是最好的方法，可以直接修改前一題自頂向下的作法並改成回溯法的方式來做，因為是要找到所有的排列組合，所以會需要遍歷所有的情況，這時候就不需要使用記憶法來記錄子問題。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordDict = set(wordDict)
ans = []
def dfs(i, candidate):
if i == len(s):
ans.append(" ".join(candidate))
return True
res = False
for word in wordDict:
if len(s[i:]) >= len(word):
if s[i:i + len(word)] == word:
candidate.append(word)
if dfs(i + len(word), candidate):
res = True
candidate.pop()
return res
dfs(0, [])
return ans另外判斷是否有找到目標的條件判斷也並不需要了，因此可以簡化成以下方式。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
wordDict = set(wordDict)
ans = []
def dfs(i, candidate):
if i == len(s):
ans.append(" ".join(candidate))
return
res = False
for word in wordDict:
if len(s[i:]) >= len(word):
if s[i:i + len(word)] == word:
candidate.append(word)
dfs(i + len(word), candidate)
candidate.pop()
dfs(0, [])
return ans