# Question

Formatted question description: https://leetcode.ca/all/139.html

139	Word Break

Given a string s and a dictionary of words dict,
determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".



# Algorithm

### Recursion

The memory array memo[i] is defined as whether the substring in the range [i, n] can be split, initialized to -1, which means that it has not been calculated, if it can be split, it is assigned a value of 1, otherwise it is 0.

Use a start variable to mark the position of the segment, so that the recursive function only needs to traverse from the start position and then the memory array memo.

### DP

• Use dict array to mark index in string
• not trying every combination of string’s substring

A one-dimensional dp array, where dp[i] indicates whether the substrings in the range [0, i) can be split.

Note that the length of the dp array is 1 greater than the length of the s string because of the need to handle an empty string. Initialize dp[0] to true.

Then start traversal. Note that two for loops are needed to traverse, because there is no recursive function at this time, so we must traverse all the substrings, and divide the substrings in the range of [0, i) into two parts with j, [0, j) and [j, i)

• where the range [0, j) is dp[j], and the range [j, i) is s.substr(j, ij),
• where dp[j] is the previous state, which has been calculated already. You only need to look up whether s.substr(j, ij) exists in the dictionary.

If both are true, assign dp[i] to true and break off, so you don’t need to use j to divide the range of [0, i), because the range of [0, i) can be split. Finally returns the last value of the dp array.

Java