原题链接: http://oj.leetcode.com/problems/word-break-ii/ 
这道题目要求跟Word Break比较类似，不过返回的结果不仅要知道能不能break，如果可以还要返回所有合法结果。一般来说这种要求会让动态规划的效果减弱很多，因为我们要在过程中记录下所有的合法结果，中间的操作会使得算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面需要历史信息会取不到。所以这道题目我们介绍两种方法，一种是直接brute force用递归解，另一种是跟Word Break思路类似的动态规划。
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。代码如下：

[java] view plaincopy

 

1. public ArrayList<String> wordBreak(String s, Set<String> dict) {  
2.     ArrayList<String> res = new ArrayList<String>();  
3.     if(s==null || s.length()==0)  
4.         return res;  
5.     helper(s,dict,0,"",res);  
6.     return res;  
7. }  
8. private void helper(String s, Set<String> dict, int start, String item, ArrayList<String> res)  
9. {  
10.     if(start>=s.length())  
11.     {  
12.         res.add(item);  
13.         return;  
14.     }  
15.     StringBuilder str = new StringBuilder();  
16.     for(int i=start;i<s.length();i++)  
17.     {  
18.         str.append(s.charAt(i));  
19.         if(dict.contains(str.toString()))  
20.         {  
21.             String newItem = item.length()>0?(item+" "+str.toString()):str.toString();  
22.             helper(s,dict,i+1,newItem,res);  
23.         }  
24.     }  
25. }  

接下来我们列出动态规划的解法，递推式跟Word Break是一样的，只是现在不只要保存true或者false，还需要保存true的时候所有合法的组合，以便在未来需要的时候可以得到。不过为了实现这点，代码量就增大很多，需要一个数据结构来进行存储，同时空间复杂度变得非常高，因为所有中间组合都要一直保存。时间上还是有提高的，就是当我们需要前面到某一个元素前的所有合法组合时，我们不需要重新计算了。不过最终复杂度还是主要取决于结果的数量。代码如下：

[java] view plaincopy

 

1. class Interval {  
2.     int start;  
3.     int end;  
4.     public Interval(int start, int end) {  
5.         this.start = start; this.end = end;  
6.     }  
7.     public Interval(Interval i) {  
8.         start = i.start;  
9.         end = i.end;  
10.  }  
11. }  
12. ArrayList<ArrayList<Interval>> deepCopy(ArrayList<ArrayList<Interval>> paths) {  
13.     if (paths==null) return null;  
14.     ArrayList<ArrayList<Interval>> res = new ArrayList<ArrayList<Interval>>(paths.size());  
15.     for (int i=0; i<paths.size(); i++) {  
16.      ArrayList<Interval> path = paths.get(i);  
17.      ArrayList<Interval> copy = new ArrayList<Interval>(path.size());  
18.         for (int j=0; j<path.size(); j++) {  
19.          copy.add(new Interval(path.get(j)));  
20.      }  
21.      res.add(copy);  
22.     }  
23.     return res;  
24. }  
25. public ArrayList<String> wordBreak(String s, Set<String> dict) {  
26.     ArrayList<String> res = new ArrayList<String>();  
27.     if (s==null || s.length()==0) return res;  
28.     Map<Integer, ArrayList<ArrayList<Interval>>> dp = new HashMap<Integer, ArrayList<ArrayList<Interval>>>();  
29.     dp.put(0, new ArrayList<ArrayList<Interval>>());  
30.     dp.get(0).add(new ArrayList<Interval>());  
31.     for (int i=1; i<=s.length(); i++) {  
32.         for (int j=0; j<i; j++) {  
33.             String cur = s.substring(j, i);  
34.             ArrayList<ArrayList<Interval>> paths = null;  
35.             if (dp.containsKey(j) && dict.contains(cur)) {  
36.                 paths = deepCopy(dp.get(j));  
37.                 Interval interval = new Interval(j, i);  
38.                 for (ArrayList<Interval> path:paths) {  
39.                     path.add(interval);  
40.                 }  
41.             }  
42.             if (paths != null) {  
43.                 if (!dp.containsKey(i)) {  
44.                     dp.put(i, paths);  
45.                 }   
46.                 else {  
47.               dp.get(i).addAll(paths);  
48.              }  
49.             }  
50.         }  
51.     }  
52.     if (!dp.containsKey(s.length())) {  
53.         return res;  
54.     }  
55.     ArrayList<ArrayList<Interval>> paths = dp.get(s.length());  
56.     for (int j=0; j<paths.size(); j++) {  
57.         ArrayList<Interval> path = paths.get(j);  
58.         StringBuilder str = new StringBuilder();  
59.         for (int i=0; i<path.size(); i++) {  
60.             if (i!=0) {str.append(" ");}  
61.             int start = path.get(i).start;  
62.             int end = path.get(i).end;  
63.             str.append(s.substring(start, end));  
64.         }  
65.         res.add(str.toString());  
66.     }  
67.     return res;  
68. }  

可以看出，用动态规划的代码复杂度要远远高于brute force的解法，而且本质来说并没有很大的提高，甚至空间上还是一个暴涨的情况。所以这道题来说并不是一定要用动态规划，有一个朋友在面Amazon时遇到这道题，面试官并没有要求动态规划，用brute force即可，不过两种方法时间上和空间上的优劣还是想清楚比较好，面试官可能想听听理解。实现的话可能主要是递归解法。
还有一点需要指出的是，上面的两个代码放到LeetCode中都会超时，原因是LeetCode中有一个非常tricky的测试case，其实是不能break的，但是又很长，出现大量的记录和回溯，因此一般通过这个的解法是把Word Break先跑一遍，判断是不是能break，如果可以再跑上面的代码。这样做法其实比较傻，但是为了过这个只能这样了，这一点我觉得LeetCode没必要把超时设得这么严格，实际意义不大，只是把AC率给拉了下来哈。

阅读全文……

发表评论

IT瘾于2015年4月1日 下午06时24分00秒发布 #