# Leetcode 139 - Word break

`DP`

- This is a
`complete knapsack`

problem. - The DP deduction is
`DP[j] = isValid(word) && DP[j-word]`

- We’d better iterate
`j`

(backpack) first because we care about the`order of elements`

.

`Backtracking`

- Easier to come up with a solution but we have to optimize, otherwise TLE.
- Use
`memo[startIndex]`

(This is particularly useful to result that is`false`

, for example:`"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]`

)- By quickly remembering
`backtracking(startIndex) == false`

, we can quickly terminate unuseful recursions.

- By quickly remembering
- Note that
`memo[i]`

is wrong. (Btw`i`

is not accessbile outside of the`forloop`

).

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 | 1. |

`DP`

1 | /** |

`Backtracking`

1 | /** |