forked from rpj911/LeetCode_algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathWordBreak2.java
More file actions
85 lines (67 loc) · 2.45 KB
/
WordBreak2.java
File metadata and controls
85 lines (67 loc) · 2.45 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
package Algorithms;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
public class WordBreak2 {
public static void main(String[] strs) {
WordBreak2 wb = new WordBreak2();
Set<String> dict = new HashSet<String>();
/*
dict.add("cat");
dict.add("cats");
dict.add("and");
dict.add("sand");
dict.add("dog");
*/
String[] s = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
for(String s1: s) {
dict.add(s1);
}
String s3 = "yu";
String s4 = s3.substring(2);
wb.wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", dict);
}
public ArrayList<String> wordBreak(String s, Set<String> dict) {
HashMap<String, ArrayList<String>> memo = new HashMap<String, ArrayList<String>>();
return wordBreakHelp(s, dict, memo, getMaxLen(dict));
}
private ArrayList<String> wordBreakHelp(String s, Set<String> dict, HashMap<String, ArrayList<String>> memo, int max) {
// this is cutting branch. We don't need to count the duplicate strings.
ArrayList<String> rst = memo.get(s);
if (rst != null) {
return rst;
}
rst = new ArrayList<String>();
if (s.length() == 0) {
return rst;
}
int len = Math.min(max, s.length());
for (int i = 0; i < len; i++) {
String pre = s.substring(0, i + 1);
// if the pre is not a word, just continue;
if (!dict.contains(pre)) {
continue;
}
if (i == s.length() - 1) {
rst.add(pre);
break;
}
ArrayList<String> tmp = wordBreakHelp(s.substring(i + 1), dict, memo, max);
// the tail can't be divided;
for(String s1: tmp) {
String newStr = pre + " " + s1;
rst.add(newStr);
}
}
memo.put(s, rst);
return rst;
}
private int getMaxLen(Set<String> dict) {
int max = 0;
for(String s: dict) {
max = Math.max(max, s.length());
}
return max;
}
}