I know others have better solutions using BFS or DFS. However, I first solved this problem using dynamic programming and I didn't check the tag at that time. I tested on my local machine and the result was correct and I submitted my solution but I didn't even pass the first test case. It gives me an error message of "time exceeded". I am wondering if there is a better way of using dynamic programming.

Basically, what I did was to start from the first character of the string and test if it can be formed from strings in the set. I also use a boolean array to save this information then I add the next character from the string and test and so forth. Below is my code.

```
public boolean wordBreak(String s, Set<String> dict) {
if (s==null) return false;
if (s.equals("")) return false;
int size=s.length();
boolean[] contained=new boolean[s.length()+1];
contained[0]=true;
for (int i=0;i<size;i++){
for (int j=i;j>=0;j--){
if (dict.contains(s.substring(j,i+1))&&contained[j]){
contained[i+1]=true;
break;
}
contained[i+1]=false;
}
}
return contained[size];
}
```