# [LeetCode 139] Word Break

### 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];
}
``````