Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, determine ifscan 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 `word`

s 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]
```