|
1 | 1 | packageAlgorithms.dp; |
2 | 2 |
|
| 3 | + |
3 | 4 | importjava.util.ArrayList; |
4 | 5 | importjava.util.HashMap; |
| 6 | +importjava.util.HashSet; |
5 | 7 | importjava.util.List; |
6 | 8 | importjava.util.Set; |
7 | 9 |
|
8 | 10 | publicclassWordBreak2 { |
| 11 | +publicstaticvoidmain(String[]strs) { |
| 12 | +Strings ="aaaaaaaaaaaaaaaaaaaaaaa"; |
| 13 | +Set<String>dict =newHashSet<String>(); |
| 14 | +dict.add("bin"); |
| 15 | +dict.add("apple"); |
| 16 | +dict.add("app"); |
| 17 | +dict.add("le"); |
| 18 | +dict.add("aaaaaa"); |
| 19 | +dict.add("aaaaa"); |
| 20 | +dict.add("aaaa"); |
| 21 | +dict.add("aaa"); |
| 22 | +dict.add("aa"); |
| 23 | +dict.add("a"); |
| 24 | +dict.add("aaaaaaa"); |
| 25 | +dict.add("aaaaaaaa"); |
| 26 | +dict.add("aaaaaaaaa"); |
| 27 | + |
| 28 | +System.out.println("Test"); |
| 29 | + |
| 30 | +Algorithms.permutation.Stopwatchtimer1 =newAlgorithms.permutation.Stopwatch(); |
| 31 | + |
| 32 | +// 递归模板，加剪枝 |
| 33 | +List<String>list =wordBreak(s,dict); |
| 34 | + |
| 35 | +System.out |
| 36 | + .println("Computing time with dfs and cut branch used as Queue/Deque: " |
| 37 | + +timer1.elapsedTime() +" millisec."); |
| 38 | + |
| 39 | +Algorithms.permutation.Stopwatchtimer2 =newAlgorithms.permutation.Stopwatch(); |
| 40 | + |
| 41 | +// HASH保存记忆 |
| 42 | +List<String>list2 =wordBreak1(s,dict); |
| 43 | + |
| 44 | +System.out |
| 45 | + .println("Computing time with ArrayDeque used as Queue/Deque: " |
| 46 | + +timer2.elapsedTime() +" millisec."); |
| 47 | + |
| 48 | +//System.out.println(list.toString()); |
| 49 | + } |
| 50 | + |
9 | 51 | // 我们用DFS来解决这个问题吧 |
10 | 52 | publicstaticList<String>wordBreak1(Strings,Set<String>dict) { |
11 | 53 | HashMap<String,List<String>>map =newHashMap<String,List<String>>(); |
@@ -69,7 +111,6 @@ public static List<String> dfs(String s, Set<String> dict, HashMap<String, List< |
69 | 111 |
|
70 | 112 | // 我们用DFS来解决这个问题吧 |
71 | 113 | publicstaticList<String>wordBreak(Strings,Set<String>dict) { |
72 | | -HashMap<String,List<String>>map =newHashMap<String,List<String>>(); |
73 | 114 | if (s ==null ||s.length() ==0 ||dict ==null) { |
74 | 115 | returnnull; |
75 | 116 | } |
|