本文主要是介绍LeetCode--140. Word Break II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题链接：https://leetcode.com/problems/word-break-ii/
这是紧接着Word Break I的问题，难度上更大，因为要记录所有切分结果所以动态规划的方法就不太奏效了，先复习一下这个问题的算法：dp[i]表示字串0-i是否存在一个切分使得切分后的各个部分都在字典中，状态转移方程为：
j exists in [0,i-1], make dp[i]=dp[j] && sub[j...i] in dict
这个求dp[i]的子问题与整个问题是一致的。
class Solution {public boolean wordBreak(String s, List<String> wordList){if (s == null || s.length() == 0) return false;int n = s.length();Set<String> set = new HashSet<>();for (String word : wordList) set.add(word);boolean[] dp = new boolean[n];for (int i = 0; i < n; i++) //外循环是填写dp数组的过程{for (int j = 0; j <= i; j++) //内循环是找符合条件的前缀和存在于字典中的子字符串（前缀串与该子字符串组成当前结尾于i位置的前缀串）{String sub = s.substring(j, i + 1);if (set.contains(sub) && (j == 0 || dp[j - 1])){dp[i] = true;break;}}}return dp[n - 1];}
}
再来看Word Break II，可以使用一个数据结构记录下目标字符串S中S[i:j]存在于字典的字串对应的i和j，然后进行搜索拼接。搜索拼接的过程使用深度优先搜索或者while循环可以完成，这里就很类似于https://blog.csdn.net/To_be_to_thought/article/details/86536143中LeetCode--392. Is Subsequence的搜索拼接方法（问题一思路二）
代码如下：
public class WordBreakII {public static List<String> rst;public static List<String> wordBreak(String s, Set<String> wordDict){List<Integer>[] starts = new List[s.length() + 1]; // valid start positions,the index of Array represents end index of substring starting at i that stored in Liststarts[0] = new ArrayList<>();int maxLen = getMaxLen(wordDict);for (int i = 1; i <= s.length(); i++){for (int j = i - 1; j >= i - maxLen && j >= 0; j--){if (starts[j] == null)continue;String word = s.substring(j, i);if (wordDict.contains(word)){if (starts[i] == null){starts[i] = new ArrayList<>();}starts[i].add(j);}}}rst = new ArrayList<>();if (starts[s.length()] == null){return rst;}dfs("", s, starts, s.length());return rst;}private static void dfs(String path, String s, List<Integer>[] starts, int end) {if (end == 0){rst.add(path.substring(1));return;}for (Integer start: starts[end]){String word = s.substring(start, end);dfs(" " + word + path, s, starts, start);}}
}
我在Discussion区域看到了两种不太容易理解的方法，链接https://leetcode.com/problems/word-break-ii/discuss/44243/Java-DP%2BDFS-Memoization%2BDFS-and-DP-Pruning-Solutions-with-Analysis，代码也贴在这里：
public class WordBreakII {public static List<String> rst;public static List<String> wordBreak(String s, Set<String> wordDict){List<Integer>[] starts = new List[s.length() + 1]; // valid start positions,the index of Array represents end index of substring starting at i that stored in Liststarts[0] = new ArrayList<>();int maxLen = getMaxLen(wordDict);for (int i = 1; i <= s.length(); i++){for (int j = i - 1; j >= i - maxLen && j >= 0; j--){if (starts[j] == null)continue;String word = s.substring(j, i);if (wordDict.contains(word)){if (starts[i] == null){starts[i] = new ArrayList<>();}starts[i].add(j);}}}rst = new ArrayList<>();if (starts[s.length()] == null){return rst;}dfs("", s, starts, s.length());return rst;}private static void dfs(String path, String s, List<Integer>[] starts, int end) {if (end == 0){rst.add(path.substring(1));return;}for (Integer start: starts[end]){String word = s.substring(start, end);dfs(" " + word + path, s, starts, start);}}private static int getMaxLen(Set<String> wordDict){int max = 0;for (String s : wordDict){max = Math.max(max, s.length());}return max;}public static HashMap<Integer, List<String>> memo;public static List<String> wordBreak1(String s, Set<String> wordDict){memo = new HashMap<>(); // <Starting index, rst list>return dfs(s, 0, wordDict);}private static List<String> dfs(String s, int start, Set<String> dict){if (memo.containsKey(start)){return memo.get(start);}List<String> rst = new ArrayList<>();if (start == s.length()){rst.add("");return rst;}String curr = s.substring(start);for (String word: dict){if (curr.startsWith(word)){List<String> sublist = dfs(s, start + word.length(), dict);for (String sub : sublist){rst.add(word + (sub.isEmpty() ? "" : " ") + sub);}}}memo.put(start, rst);return rst;}public static List<String> ret;public static List<String> wordBreak2(String s, Set<String> wordDict){ret = new ArrayList<>();if (s == null || s.length() == 0 || wordDict == null){return ret;}//whether a substring starting from position i to the end is breakableboolean[] canBreak = new boolean[s.length()];Arrays.fill(canBreak, true);StringBuilder sb = new StringBuilder();dfs(sb, s, wordDict, canBreak, 0);return ret;}private static void dfs(StringBuilder sb, String s, Set<String> dict, boolean[] canBreak, int start){if (start == s.length()){ret.add(sb.substring(1));return;}if (!canBreak[start]){return;}for (int i = start + 1; i <= s.length(); i++){String word = s.substring(start, i);if (!dict.contains(word))continue;int sbBeforeAdd = sb.length();sb.append(" " + word);int rstBeforeDFS = ret.size();dfs(sb, s, dict, canBreak, i);if (ret.size() == rstBeforeDFS){canBreak[i] = false;}sb.delete(sbBeforeAdd, sb.length());}}public static void main(String[] args){String s="catsanddog";String[] strs={"cat", "cats", "and", "sand", "dog"};Set<String> dict=new HashSet<>();for(String str:strs)dict.add(str);wordBreak(s,dict);List<String> tmp=wordBreak1(s,dict);wordBreak2(s,dict);}
}
这篇关于LeetCode--140. Word Break II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
