@@ -27,32 +27,32 @@ public static void main(String[] strs) {
2727
2828System .out .println ("Test" );
2929
30- Algorithms .permutation .Stopwatch timer1 =new Algorithms .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-
3930Algorithms .permutation .Stopwatch timer2 =new Algorithms .permutation .Stopwatch ();
4031
4132// HASH保存记忆
4233wordBreak1 (s ,dict );
4334
4435System .out
45- .println ("Computing time withArrayDeque used as Queue/Deque : "
36+ .println ("Computing time withDFS1 : "
4637 +timer2 .elapsedTime () +" millisec." );
4738
39+ Algorithms .permutation .Stopwatch timer1 =new Algorithms .permutation .Stopwatch ();
40+
41+ // 递归模板，加剪枝
42+ wordBreak (s ,dict );
43+
44+ System .out
45+ .println ("Computing time with DFS2: "
46+ +timer1 .elapsedTime () +" millisec." );
47+
4848Algorithms .permutation .Stopwatch timer3 =new Algorithms .permutation .Stopwatch ();
4949
5050// DFS+ 剪枝 3: 设置Flag 变量
5151//http://fisherlei.blogspot.com/2013/11/leetcode-wordbreak-ii-solution.html
5252wordBreak3 (s ,dict );
5353
5454System .out
55- .println ("Computing time withArrayDeque used as Queue/Deque : "
55+ .println ("Computing time withDFS3 : "
5656 +timer3 .elapsedTime () +" millisec." );
5757
5858//System.out.println(list.toString());
@@ -207,32 +207,6 @@ public static boolean iswordBreak(String s, Set<String> dict) {
207207return D [len ];
208208 }
209209
210- /*
211- // 解法3：重新剪枝。
212- */
213-
214- // 我们用DFS来解决这个问题吧
215- public static List <String >wordBreak3 (String s ,Set <String >dict ) {
216- if (s ==null ||s .length () ==0 ||dict ==null ) {
217- return null ;
218- }
219-
220- List <String >ret =new ArrayList <String >();
221-
222- // 记录切割过程中生成的字母
223- List <String >path =new ArrayList <String >();
224-
225- int len =s .length ();
226- boolean canBreak [] =new boolean [len ];
227- for (int i =0 ;i <len ;i ++) {
228- canBreak [i ] =true ;
229- }
230-
231- dfs3 (s ,dict ,path ,ret ,0 ,canBreak );
232-
233- return ret ;
234- }
235-
236210// 我们用DFS模板来解决这个问题吧
237211public static void dfs3 (String s ,Set <String >dict ,
238212List <String >path ,List <String >ret ,int index ,
@@ -256,23 +230,25 @@ public static void dfs3(String s, Set<String> dict,
256230return ;
257231 }
258232
259- boolean flag =false ;
260233for (int i =index ;i <len ;i ++) {
261234// 注意这些索引的取值。左字符串的长度从0到len
262235String left =s .substring (index ,i +1 );
263- if (!dict .contains (left )) {
236+ if (!dict .contains (left ) || ! canBreak [ i + 1 ] ) {
264237// 如果左字符串不在字典中，不需要继续递归
265238continue ;
266239 }
267240
268241// if can't find any solution, return false, other set it
269242// to be true;
270- flag =true ;
271243path .add (left );
244+
245+ int beforeChange =ret .size ();
272246dfs3 (s ,dict ,path ,ret ,i +1 ,canBreak );
247+ // 注意这些剪枝的代码. 关键在于此以减少复杂度
248+ if (ret .size () ==beforeChange ) {
249+ canBreak [i +1 ] =false ;
250+ }
273251path .remove (path .size () -1 );
274252 }
275-
276- canBreak [index ] =flag ;
277253 }
278254}