Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Example 1: Input: s = “leetcode”, wordDict = [“leet”,“code”] Output: true Explanation: Return true because “leetcode” can be segmented as “leet code”.
- code bfs with string
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
q = deque(wordDict)
seen = set(wordDict)
while q:
cur = q.popleft()
if s == cur:
return True
if s.startswith(cur):
for word in wordDict:
nex = cur + word
if nex not in seen:
q.append(nex)
seen.add(nex)
return False
- code bfs with index
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
word_set = set(wordDict)
q = deque([0])
visited = set([0])
while q:
start = q.popleft()
for end in range(start + 1, len(s) + 1):
if s[start:end] in word_set and end not in visited:
if end == len(s):
return True
visited.add(end)
q.append(end)
return False
- code memo
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
memo = {}
def helper(target):
if target in memo: return memo[target]
if not target: return True
for word in wordDict:
if target.startswith(word):
memo[target] = helper(target[len(word):])
if memo[target]: return True
memo[target] = False
return False
return helper(s)
- code
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@lru_cache
def helper(target):
if not target: return True
for word in wordDict:
if target.startswith(word):
if helper(target[len(word):]): return True
return False
return helper(s)
- code
class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [False] * (len(s) + 1)
dp[0] = True
for i in range(len(dp)):
if dp[i]:
for word in wordDict:
if s[i:].startswith(word):
dp[i + len(word)] = True
return dp[-1]