首页 > 代码库 > [leecode]Word Break II
[leecode]Word Break II
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, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].A solution is
["cats and dog", "cat sand dog"].
建议做这道题的时候先看下[leetcode]Word Break。
算法思路：
1. 同[leetcode]Word Break，从每一个index遍历字典，找到可以跳达的下标cover[index]；不过本地在维护一个map，记录该下标是从哪个下标跳过来的。可能是个list。例如题目中的index = 6 ，可以从下标为2，和3 跳过来。
2.1. 如果cover[length - 1] = false，则表示不可拆分，直接返回一个空list；
2.2 如果length可达，那么好了，根据map可以建立一个树，这个树的根节点肯定是length，叶节点肯定是0，因为无论怎么个跳法，最后一个下标总是从第一个下标跳过来的。
例如题目中的s=“catsanddog”
同[leetcode]Word Break，我们从1开始记录。
最后一个字符g的下标为10.10的前驱是sand中的d->7，而7的前驱是3 & 4，3 & 4 的前驱都是0；
因此这棵树的结构应该是这样的。
10
|
7
/ \
3 4
/ \
0 0
因此我们就可以用dfs，将结果返回。
代码如下：
1 public class Solution { 2 List<String> res = new ArrayList<String>(); 3 public List<String> wordBreak(String s, Set<String> dict) { 4 if(s == null || s.length() == 0) return res; 5 Map<Integer,List<Integer>> pre = new HashMap<Integer,List<Integer>>(); 6 int length = s.length(); 7 boolean[] cover = new boolean[length + 1]; 8 cover[0] = true; 9 for(int i = 0; i <= length; i++){10 if(!cover[i]) continue;11 for(String word: dict){12 if(s.substring(i).startsWith(word)){13 int stretch = i + word.length();14 if(!cover[stretch]){15 cover[stretch] = true;16 List<Integer> list = new ArrayList<Integer>();17 list.add(i);18 pre.put(stretch,list);19 }else{20 pre.get(stretch).add(i);21 }22 }23 }24 }25 if(!cover[length]) return res;26 List<String> list = new LinkedList<String>();27 getList(list,length,s,pre);28 return res;29 }30 private void getList(List<String> list,int index,String s,Map<Integer,List<Integer>> preMap){31 if(index == 0){32 StringBuilder sb = new StringBuilder();//其实递归过程中可以直接用sb的，但是感觉没有list方便，因此偷了一个懒33 for(String str : list){34 sb.append(str).append(" ");35 }36 res.add(sb.toString().trim());37 return;38 }39 List<Integer> preList = preMap.get(index);40 for(int pre:preList){41 String str = s.substring(pre,index);42 list.add(0,str);43 getList(list,pre,s,preMap);44 list.remove(0);45 }46 }47 }
[leecode]Word Break II