Many elegent algorithms such as DP and BFS are provided in the forum, and I want to show you the DFS method, which is also a good method to solve this problem.

```
public class Solution {
private boolean[] mark;
private int len;
public boolean wordBreak(String s, Set<String> dict) {
// DFS use stack optimization 150ms
if (dict.contains(s)) return true;
len = s.length();
mark = new boolean[len + 1];
java.util.LinkedList<Integer> stack = new java.util.LinkedList<Integer>();
stack.push(0);
while (!stack.isEmpty()) {
int l = stack.pop();
mark[l] = true;
for (int r = l + 1; r <= len; r++) {
if (dict.contains(s.substring(l, r)) && !mark[r]) {
if (r == len) return true;
stack.push(r);
}
}
}
return false;
}
}
```