首页 > 代码库 > Leetcode: Word Break II
Leetcode: Word Break II
Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.Return all such possible sentences.For example, givens = "catsanddog",dict = ["cat", "cats", "and", "sand", "dog"].A solution is ["cats and dog", "cat sand dog"].
难度：98，参考了别人的思路：这道题目要求跟Word Break比较类似，不过返回的结果不仅要知道能不能break，如果可以还要返回所有合法结果。一般来说这种要求会让动态规划的效果减弱很多，因为我们要在过程中记录下所有的合法结果，中间的操作会使得算法的复杂度不再是动态规划的两层循环，因为每次迭代中还需要不是constant的操作，最终复杂度会主要取决于结果的数量，而且还会占用大量的空间，因为不仅要保存最终结果，包括中间的合法结果也要一一保存，否则后面需要历史信息会取不到。所以这道题目我们介绍两种方法，一种是直接brute force用递归解，另一种是跟Word Break思路类似的动态规划。
对于brute force解法，代码比较简单，每次维护一个当前结果集，然后遍历剩下的所有子串，如果子串在字典中出现，则保存一下结果，并放入下一层递归剩下的字符。思路接近于我们在N-Queens这些NP问题中经常用到的套路。
brute force做法，类似于NP做法：
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中的DP做法，其实就是在word break的基础上稍作修改：
1 public class Solution { 2 public List<String> wordBreak(String s, Set<String> dict) { 3 ArrayList<ArrayList<String>> results = new ArrayList<ArrayList<String>>(); 4 if (s == null || s.length() == 0) return null; 5 boolean[] res = new boolean[s.length()+1]; 6 res[0] = true; 7 for (int k=0; k<=s.length(); k++) { 8 results.add(new ArrayList<String>()); 9 }10 results.get(0).add("");11 12 for (int i=1; i<=s.length(); i++) {13 for (int j=0; j<i; j++) {14 StringBuffer str = new StringBuffer(s.substring(j, i));15 if (res[j] && dict.contains(str.toString())) {16 res[i] = true;17 for (String kk : results.get(j)) {18 if (kk.equals(""))19 results.get(i).add(String.format("%s", str));20 else21 results.get(i).add(String.format("%s %s", kk, str));22 }23 }24 }25 }26 return results.get(s.length());27 }28 }
还有一点需要指出的是，上面的两个代码放到LeetCode中都会超时，原因是LeetCode中有一个非常tricky的测试case，其实是不能break的，但是又很长，出现大量的记录和回溯
有一个人有好的做法：http://www.binglu.me/leetcode-word-break-and-word-break-ii/ 可以不超时
Leetcode: Word Break II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。