139. Word Break
每次檢查一個單字,看看單字有沒有符合是目標字串的前綴字元,如果說有符合的話,繼續從剩的字串檢查下去,剩餘的字串起始位置是符合的單字的長度。
遞迴
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict = set(wordDict)
def helper(s):
if len(s) == 0:
return True
for word in wordDict:
if len(word) <= len(s):
if s.startswith(word):
if helper(s[len(word):]):
return True
return False
return helper(s)
遞迴的方式有很多重複的子問題,例如目標字串是 code
,字典是:[c, o, co, de]
,de
就是重疊子問題,所以所以利用記憶法來避免重複的子問題。
自頂向下
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDict = set(wordDict)
memo = {}
def helper(s):
if len(s) == 0:
return True
if s in memo:
return memo[s]
for word in wordDict:
if len(word) <= len(s):
if s.startswith(word):
if helper(s[len(word):]):
memo[s] = True
return memo[s]
memo[s] = False
return memo[s]
return helper(s)
自底向上
做法有點不直覺,處理的邏輯是一步一步走,去檢查每一個位置,有沒有機會可以用任何字典中的單字拼起來。檢查的邏輯如下:
例如:我站在某位置 j
,接著我就從位置 i = 0
一路檢查到位置 j
,看看有沒有辦法在位置 i
的地方其中 s[i:j]
剛好在字典裡面,但是這樣還不夠,那就是在位置 i
的地方,也要有字串可以到達才夠,如果兩個條件都滿足,那 dp[j]
就會是 True ,代表可以到達這個地方。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
for end in range(1, len(s)+1):
for start in range(end):
if dp[start] and s[start:end] in wordDict:
dp[end] = True
break
return dp[len(s)]
回溯法
這一題其實也可以用回溯法來寫,道理很類似,回溯法也是遞迴的一種,只要加上記憶法就可以了。
這樣的寫法值得參考是因為這個題目的變形,困難難度的題目,就可以用回溯法來寫。
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
wordDictSet = set(wordDict)
memo = {}
ans = []
def helper(s, curr):
if len(s) == 0:
ans.append(' '.join(curr))
return True
if s in memo:
return memo[s]
else:
for word in wordDictSet:
if len(word) <= len(s):
if s.startswith(word):
curr.append(word)
if helper(s[len(word):], curr):
memo[s[len(word):]] = True
return memo[s[len(word):]]
curr.pop()
memo[s] = False
return memo[s]
return helper(s, [])