# [Leetcode]139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
Note:
The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Input: s = "leetcode", wordDict = ["leet", "code"] Output: true

When I saw this question I recognized it as a search problem. Treating each word in the wordDict as a node, the question is asking whether or not could we found a root-to-leaf path such that the nodes along the path compose the input string s. Therefore algorithms like DFS could work. On top of that, if you know Depth-First-Search(DFS) vs Dynamic Programming(DP), we can actually improve the time efficiency by applying dynamic programming.

#### DP1. Top-down with memo

We use i to indicate the current position. If we find some words in wordDict such that s[i:i+len(word)] matches, then we can move forward to check s[i+len(word):]. We can use recursion to implement this process and the exit condition would be when we finishing scanning the whole input string s.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
@lru_cache(None)
def helper(index=0):
if index == len(s):
return True
return any(helper(index+len(word)) for word in wordDict\
if index+len(word)<=len(s) and s[index:index+len(word)] == word)
return helper()


#### DP2. Bottom-up

Or simply we could implement a dp array where dp[i] indicates whether s[:i+1] could be successfully segmented. With bottom-up approach, we would look back when determine dp[i] – to check if s[i:j] is in wordDict and dp[i] is True.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [1] # dp[i] means s[:i] could be segmented as required
for i in range(1,len(s)+1):
dp += [any(dp[j] and s[j:i] in wordDict for j in range(i))]
return dp[-1]


Or if we look forward during the loop – when processing dp[i], we set the value for dp[i+len(word)] if s[i:i+len(word)] is in wordDict.

class Solution:
def wordBreak(self, s: str, wordDict: List[str]) -> bool:
dp = [0] * (len(s)+1)
dp[0] = 1
for i in range(len(s)+1):
if dp[i]:
for word in wordDict:
if s[i:i+len(word)]==word:
dp[i+len(word)] = 1
return dp[-1]

Subscribe
Notify of