@@ -39,11 +39,21 @@ public static void main(String[] strs) {
3939Algorithms .permutation .Stopwatch timer2 =new Algorithms .permutation .Stopwatch ();
4040
4141// HASH保存记忆
42- List < String > list2 = wordBreak1 (s ,dict );
42+ wordBreak1 (s ,dict );
4343
4444System .out
4545 .println ("Computing time with ArrayDeque used as Queue/Deque: "
4646 +timer2 .elapsedTime () +" millisec." );
47+
48+ Algorithms .permutation .Stopwatch timer3 =new Algorithms .permutation .Stopwatch ();
49+
50+ // DFS+ 剪枝 3: 设置Flag 变量
51+ //http://fisherlei.blogspot.com/2013/11/leetcode-wordbreak-ii-solution.html
52+ wordBreak3 (s ,dict );
53+
54+ System .out
55+ .println ("Computing time with ArrayDeque used as Queue/Deque: "
56+ +timer3 .elapsedTime () +" millisec." );
4757
4858//System.out.println(list.toString());
4959 }
@@ -126,7 +136,8 @@ public static List<String> wordBreak(String s, Set<String> dict) {
126136 }
127137
128138// 我们用DFS模板来解决这个问题吧
129- public static void dfs2 (String s ,Set <String >dict ,List <String >path ,List <String >ret ,int index ) {
139+ public static void dfs2 (String s ,Set <String >dict ,
140+ List <String >path ,List <String >ret ,int index ) {
130141int len =s .length ();
131142if (index ==len ) {
132143// 结束了。index到了末尾
@@ -195,4 +206,73 @@ public static boolean iswordBreak(String s, Set<String> dict) {
195206
196207return D [len ];
197208 }
209+
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+
236+ // 我们用DFS模板来解决这个问题吧
237+ public static void dfs3 (String s ,Set <String >dict ,
238+ List <String >path ,List <String >ret ,int index ,
239+ boolean canBreak []) {
240+ int len =s .length ();
241+ if (index ==len ) {
242+ // 结束了。index到了末尾
243+ StringBuilder sb =new StringBuilder ();
244+ for (String str :path ) {
245+ sb .append (str );
246+ sb .append (" " );
247+ }
248+ // remove the last " "
249+ sb .deleteCharAt (sb .length () -1 );
250+ ret .add (sb .toString ());
251+ return ;
252+ }
253+
254+ // if can't break, we exit directly.
255+ if (!canBreak [index ]) {
256+ return ;
257+ }
258+
259+ boolean flag =false ;
260+ for (int i =index ;i <len ;i ++) {
261+ // 注意这些索引的取值。左字符串的长度从0到len
262+ String left =s .substring (index ,i +1 );
263+ if (!dict .contains (left )) {
264+ // 如果左字符串不在字典中，不需要继续递归
265+ continue ;
266+ }
267+
268+ // if can't find any solution, return false, other set it
269+ // to be true;
270+ flag =true ;
271+ path .add (left );
272+ dfs3 (s ,dict ,path ,ret ,i +1 ,canBreak );
273+ path .remove (path .size () -1 );
274+ }
275+
276+ canBreak [index ] =flag ;
277+ }
198278}