Word Break II

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"].
Solution:
1. public class Solution {
2. public List wordBreak(String s, Set dict) {
3. List res = new ArrayList();
4. 5. if (!canBreak(s, dict)) return res;
6. 7. helper(s, dict, 0, "", res);
8. 9. return res;
10. }
11. 12. void helper(String s, Set dict, int start, String sol, List res) {
13. if (start == s.length()) {
14. res.add(sol);
15. return;
16. }
17. 18. for (int i = start; i < s.length(); i++) {
19. String sub = s.substring(start, i + 1);
20. 21. if (dict.contains(sub)) {
22. helper(s, dict, i + 1, sol + (sol.length() == 0 ? "" : " ") + sub, res);
23. }
24. }
25. }
26. 27. boolean canBreak(String s, Set dict) {
28. if (s == null || s.length() == 0) return false;
29. 30. int n = s.length();
31. 32. // dp[i] represents whether s[0...i] can be formed by dict
33. boolean[] dp = new boolean[n];
34. 35. for (int i = 0; i < n; i++) {
36. for (int j = 0; j <= i; j++) {
37. String sub = s.substring(j, i + 1);
38. 39. if (dict.contains(sub) && (j == 0 || dp[j - 1])) {
40. dp[i] = true;
41. break;
42. }
43. }
44. }
45. 46. return dp[n - 1];
47. }
48. }