本题跟一般DFS不同的是，需要先利用Word Break I 的结果来判断是否能Break，如果不能break，直接裸上DFS，会超时。check 完是否能Break之后就跟一般DFS 一样了。(一般来说，如果不check且不能break，DFS在忙活一阵之后会返回一个空List，但OJ贱贱的有一个很大且不能break的test case，而据我猜测，能break的case都相对比较小，妈蛋！所以OJ用这种很贱的方式来强迫你先check，再DFS）。

public class Solution {

public List<String> wordBreak(String s, Set<String> dict) {

List<String> result = new ArrayList<String>();

StringBuilder sb = new StringBuilder();

if(canBreak(s, dict)) dfs(s, 0, dict, sb, result);

return result;

}

public boolean canBreak(String s, Set<String> dict) {

if(s == null || s.length() == 0) return true;

int len = s.length();

boolean[] dp = new boolean[len + 1];

dp[0] = true;

for(int i = 0; i < len; i++) {

for(int j = 0; j <= i; j++) {

if(dp[j] && dict.contains(s.substring(j, i + 1))) {

dp[i + 1] = true;

break;

}

}

}

return dp[len];

}

private void dfs(String s, int start, Set<String> dict, StringBuilder sb, List<String> result) {

if(start == s.length()) {

StringBuilder temp = new StringBuilder(sb); // 需要新建一个，不能在原来的sb上改。

temp.deleteCharAt(temp.length() - 1);

result.add(temp.toString());

} else {

for(int i = start; i < s.length(); i++) {

String temp = s.substring(start, i + 1);

if(dict.contains(temp)) {

sb.append(temp).append(" ");

dfs(s, i + 1, dict, sb, result);

sb.delete(sb.length() - temp.length() - 1, sb.length());

}

}

}

}

}