Most DP solution tries a position i as the end position, and tries a position j before i, find if dp[j] is true and substring(i, j) is in the dict.

However I try a position i as the start position, if dp[i], try every word w in dict and set dp[i + w.length()] to true

```
public boolean wordBreak(String s, List<String> wordDict) {
Set<String> set = new HashSet();
for (String w : wordDict)
set.add(w);
boolean [] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 0; i < s.length(); i++) {
if (!dp[i])
continue;
for (String w : set) {
if (s.startsWith(w, i))
dp[i + w.length()] = true;
}
}
return dp[s.length()];
}
```