题目：
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
Return all such possible sentences.
For example, given
s = "catsanddog",
dict = ["cat", "cats", "and", "sand", "dog"].
A solution is ["cats and dog", "cat sand dog"].
题解：
这道题不仅仅是看是不是wordbreak，还需要在此基础上把所有word break的结果保存。
为了把所有可能性都保存，那么就使用DFS方法来解决。DFS主要就是跳的层次不容易看出，我下面就以字符串leetcode字典le l et eet code作为例子画了一张图，大概讲解了如何递回和返回，这样更加有助于理解。
代码如下：
1 public boolean wordBreakcheck(String s, Set<String> dict) {
2 if(s==null || s.length()==0)
3 return true;
4 boolean[] res = new boolean[s.length()+1];
5 res[0] = true;
6 for(int i=0;i<s.length();i++){
7 StringBuilder str = new StringBuilder(s.substring(0,i+1));
8 for(int j=0;j<=i;j++){
9 if(res[j] && dict.contains(str.toString())){
10 res[i+1] = true;
11 break;
12 }
13 str.deleteCharAt(0);
14 }
15 }
16 return res[s.length()];
17 }
18
19 public ArrayList<String> wordBreak(String s, Set<String> dict) {
20 ArrayList<String> res = new ArrayList<String>();
21 if(s==null || s.length()==0)
22 return res;
23 if(wordBreakcheck(s,dict))
24 helper(s,dict,0,"",res);
25 return res;
26 }
27 private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res){
28 if(start>=s.length()){
29 res.add(item);
30 return;
31 }
32
33 StringBuilder str = new StringBuilder();
34 for(int i=start;i<s.length();i++){
35 str.append(s.charAt(i));
36 if(dict.contains(str.toString())){
37 String newItem = new String();
38 if(item.length()>0)
39 newItem = item + " " + str.toString();
40 else
41 newItem = str.toString();
42 helper(s,dict,i+1,newItem,res);
43 }
44 }
45 }
2 if(s==null || s.length()==0)
3 return true;
4 boolean[] res = new boolean[s.length()+1];
5 res[0] = true;
6 for(int i=0;i<s.length();i++){
7 StringBuilder str = new StringBuilder(s.substring(0,i+1));
8 for(int j=0;j<=i;j++){
9 if(res[j] && dict.contains(str.toString())){
10 res[i+1] = true;
11 break;
12 }
13 str.deleteCharAt(0);
14 }
15 }
16 return res[s.length()];
17 }
18
19 public ArrayList<String> wordBreak(String s, Set<String> dict) {
20 ArrayList<String> res = new ArrayList<String>();
21 if(s==null || s.length()==0)
22 return res;
23 if(wordBreakcheck(s,dict))
24 helper(s,dict,0,"",res);
25 return res;
26 }
27 private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res){
28 if(start>=s.length()){
29 res.add(item);
30 return;
31 }
32
33 StringBuilder str = new StringBuilder();
34 for(int i=start;i<s.length();i++){
35 str.append(s.charAt(i));
36 if(dict.contains(str.toString())){
37 String newItem = new String();
38 if(item.length()>0)
39 newItem = item + " " + str.toString();
40 else
41 newItem = str.toString();
42 helper(s,dict,i+1,newItem,res);
43 }
44 }
45 }
Reference: http://blog.csdn.net/linhuanmars/article/details/22452163