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"].

分析：

感觉用字典树可以啊，先利用dict建一棵字典树，然后从头开始匹配字符串，直到一个单词结束，然后剩下字符串重新匹配字典树。。。

如果单词的最后一个节点的子树不为空，即如字典中除了cat还有cats这种，那就匹配到s，anddog再重新匹配字典树

好像这跟暴力解法差不多，而且还需要建树，也挺耗时的！

http://blog.csdn.net/linhuanmars/article/details/22358863

擦，看了半天，发现LZ来了句，这两种解法在leetcode上都会超时，醉了。。。

http://www.programcreek.com/2014/03/leetcode-word-break-ii-java/

参考代码如下：

public class Solution {public static List<String> wordBreak(String s, Set<String> dict) {//create an array of ArrayList<String>List<String> dp[] = new ArrayList[s.length()+1];dp[0] = new ArrayList<String>();for(int i=0; i<s.length(); i++){if( dp[i] == null ) continue; for(String word:dict){int len = word.length();int end = i+len;if(end > s.length()) continue;if(s.substring(i,end).equals(word)){if(dp[end] == null){dp[end] = new ArrayList<String>();}dp[end].add(word);}}}List<String> result = new LinkedList<String>();if(dp[s.length()] == null) return result; ArrayList<String> temp = new ArrayList<String>();dfs(dp, s.length(), result, temp);return result;
}public static void dfs(List<String> dp[],int end,List<String> result, ArrayList<String> tmp){if(end <= 0){String path = tmp.get(tmp.size()-1);for(int i=tmp.size()-2; i>=0; i--){path += " " + tmp.get(i) ;}result.add(path);return;}for(String str : dp[end]){tmp.add(str);dfs(dp, end-str.length(), result, tmp);tmp.remove(tmp.size()-1);}}
}

这篇关于Word Break II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---