首页 > 代码库 > Word Break II
Word Break II
https://oj.leetcode.com/problems/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"].
这道题目与上题看似相似，其实只多一步还是有很大的区别。首先想到可以借助上题的思路，首先判断s是不是可以word break，并在这个过程中生成一个数组，每个数组是一个ArrayList，divideList[m].contains(n)就表示s.substring(m.n)在dict中。
考虑上面的例子。divideList的形式如下：
0——3，4
3——7
4——7
7——10
这是不是就是图的邻接表表示法，当然用邻接矩阵（二维数组）也是同样可以的。就是这个问题，困了我两天，期间还忙了很多事情。还是基本功不扎实。
于是剩下的问题，就是从0到10的所有可能路径。推广，找出所有可能的word break，就是找出divideList[]中所有从0到length - 1的路径。这就是图中的DFS或者BFS，可以用递归或者迭代来做。
public class Solution { public List<String> wordBreak(String s, Set<String> dict) { List<String> list = new ArrayList<String>(); boolean[] dp = new boolean[s.length()]; //一个邻接表表示的图，divideList[m] = n表示s的m到n的子串在dict中 //找出所有可能的word break，就是找出所有从0到length - 1的路径 List[] divideList = new ArrayList[s.length()]; if (s.length() == 0) { return list; } if (dict.contains(s.substring(0, 1))) { dp[0] = true; divideList[0] = new ArrayList<Integer>(); divideList[0].add(1); } for (int i = 1; i < s.length(); i++) { divideList[i] = new ArrayList<Integer>(); if (dict.contains(s.substring(0, i + 1))) { if (divideList[0] == null) { divideList[0] = new ArrayList<Integer>(); } divideList[0].add(i + 1); } for (int j = 0; j < i; j++) { if (dict.contains(s.substring(0, i + 1)) || (dp[j] == true && dict.contains(s.substring(j + 1, i + 1)))) { dp[i] = true;// divideList[i].add(j); } if (dp[j] == true && dict.contains(s.substring(j + 1, i + 1))) { divideList[j + 1].add(i + 1); } } } if (dp[s.length() - 1] == false) { return list; } //dfs divideList StringBuffer bf = new StringBuffer(); dfsStringList(s, 0, list, bf, divideList); return list; } public static void dfsStringList(String s, int start, List<String> list, StringBuffer bf, List[] divideList) { //递归结束条件，到达string的结尾 if (start == s.length()) { list.add(new String(bf)); return; } //根据divideList的定义，如果调用到这个方法，必然从divideList[0]开始 for (int i = 0; i < divideList[start].size(); i++) { int lengthBeforeAppend = bf.length(); int end = (Integer) divideList[start].get(i); //每个单词后加上空格 if(lengthBeforeAppend != 0){ bf = bf.append(" "); } //将一个分词加入bf bf = bf.append(s.substring(start, end)); //对这个分词后的子串递归dfs dfsStringList(s, end, list, bf, divideList); //考虑一个例子，0——3，4；3——7；4——7；7——10。0-3结束后递归3-10 //递归结束后list.add(new String(bf));然后弹出栈，删除bf中7-10的子串，i向后，因为此时i只有一个，所以直到0，i到1，处理0-4 bf = bf.delete(lengthBeforeAppend, bf.length()); } }}
事实上，这道题，dp只用来判断是否可以word break就可以了。如果dp[s.length() - 1] == fals，直接return 空list。后面索性将dict传入dfs方法，直接做dfs，反而较为简便。问题是，没有剪枝的过程，和上述方法相比，多了不少计算。下面是网上搜索的代码，下面会说明出处。
public class Solution { public ArrayList<String> wordBreak(String s, Set<String> dict) { ArrayList<String> ret = new ArrayList<String>(); if (s==null || s.length()==0) return ret; int n = s.length(); boolean[] dp = new boolean[n+1]; dp[0] = true; for (int i=1; i<=n; i++) { if (dict.contains(s.substring(0, i))) { dp[i] = true; continue; } for (int j=0; j<i; j++) { if (dp[j] && dict.contains(s.substring(j, i))) { dp[i] = true; } } } if (dp[n] == false) return ret; //DP的作用就这一行！！！ StringBuilder cur = new StringBuilder(); dfs(s, 0, cur, ret, dict); return ret; } public void dfs(String s, int start, StringBuilder cur, ArrayList<String> ret, Set<String> dict) { int n = s.length(); if (start >= n) { ret.add(new String(cur)); return; } for (int i=start+1; i<=n; i++) { String sub = s.substring(start, i); if (dict.contains(sub)) { int oldLen = cur.length(); if (oldLen!=0) cur.append(" "); cur.append(sub); dfs(s, i, cur, ret, dict); cur.delete(oldLen, cur.length()); } } }}
参考地址：
https://stupidcodergoodluck.wordpress.com/2013/11/16/leetcode-word-break-ii/
http://www.cnblogs.com/feiling/p/3357067.html
http://www.acmerblog.com/word-break-ii-6128.html
http://fisherlei.blogspot.jp/2013/11/leetcode-wordbreak-ii-solution.html
Word Break II