Word Break II

 1 public class Solution {
 2     public ArrayList<String> wordBreak(String s, Set<String> dict) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         ArrayList<String> result = new ArrayList<String>();
 6         if (s == null || dict.size() <= 0) {
 7             return result;
 8         }
 9         int length = s.length();
10         // seg(i, j) means substring t start from i and length is j can be
11         // segmented into
12         // dictionary words
13         boolean[][] seg = new boolean[length][length + 1];
14         for (int len = 1; len <= length; len++) {
15             for (int i = 0; i < length - len + 1; i++) {
16                 String t = s.substring(i, i + len);
17                 if (dict.contains(t)) {
18                     seg[i][len] = true;
19                     continue;
20                 }
21                 for (int k = 1; k < len; k++) {
22                     if (seg[i][k] && seg[i + k][len - k]) {
23                         seg[i][len] = true;
24                         break;
25                     }
26                 }
27             }
28         }
29         if (!seg[0][length]) {
30             return result;
31         }
32 
33         int depth = 0;
34         dfs(s, seg, 0, length, depth, result, new StringBuffer(), dict);
35 
36         return result;
37     }
38 
39     private static void dfs(String s, boolean[][] seg, int start, int length,
40             int depth, ArrayList<String> result, StringBuffer sb, Set<String> dict) {
41         if (depth == length) {
42             String t = sb.toString();
43             result.add(t.substring(0, t.length() - 1));
44             return;
45         }
46 
47         for (int len = 1; len <= length; len++) {
48             if (seg[start][len]) {
49                 String t = s.substring(start, start + len);
50                 if(!dict.contains(t)){
51                     continue;
52                 }
53                 int beforeAddLen = sb.length();
54                 sb.append(t).append(" ");
55                 dfs(s, seg, start + len, length, start + len, result, sb, dict);
56                 sb.delete(beforeAddLen, sb.length());
57             }
58         }
59     }
60 }