### Question

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"`

.

### Stats

Adjusted Difficulty | 4 |

Time to use | -------- |

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

**This is a standard DP question**.

### Solution

I see a lot of people solve this DP problem with 2D array. It actually requires only 1D aray.

Declare an boolean array of (input string length) + 1, and dp[i] mean whether or not subtring(0,i) is work-breakable. Then the problem is clear and easy.

Pay attention to index while coding.

### Code

**my code**

```
public boolean wordBreak(String s, Set<String> dict) {
int len = s.length();
if (len == 0 || dict.isEmpty()) {
return false;
}
boolean[] dp = new boolean[len + 1];
dp[0] = true;
for (int i = 1; i <= len; i ++) {
for (int j = 0; j < i; j ++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
```