# 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.
• 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

DP

Backtracking