Last year, I failed one vital onsite because of this problem when I did not know dp. I even dreamed of it in my nightmare. Good to get over it.

```
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
Set<String> dict = new HashSet<>();
int maxLen = 0;
for(String word : wordDict) {
maxLen = Math.max(maxLen, word.length());
dict.add(word);
}
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for(int i = 0; i < n; i++) {
if(dp[i]) {
for(int j = i + 1; j <= n && j - i <= maxLen; j++) {
if(dict.contains(s.substring(i, j)) ) {
dp[j] = true;
}
}
}
}
return dp[n];
}
```