首页 > 代码库 > 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"].
参考：http://www.tuicool.com/articles/ZVJJRrF
1 import java.util.ArrayList; 2 import java.util.LinkedList; 3 import java.util.List; 4 import java.util.Set; 5 6 public class Solution { 7 public List<String> wordBreak(String s, Set<String> dict) { 8 List<String> dp[] = new ArrayList[s.length() + 1]; 9 dp[0] = new ArrayList<String>();10 11 for(int i = 0; i < s.length(); i++){12 if(dp[i] == null)13 continue;14 for(String word : dict){15 int length = word.length();16 int end = i + length;17 if(end > s.length())18 continue;19 if(s.substring(i, end).equals(word)){20 if(dp[end] == null)21 dp[end] = new ArrayList<String>();22 dp[end].add(word);23 }//if24 }//for25 }//for26 List<String> result = new LinkedList<String>();27 if(dp[s.length()] == null)28 return result;29 List<String> temp = new ArrayList<String>();30 31 dfsStringList(dp, result, s.length(), temp);32 33 return result;34 }35 36 private void dfsStringList(List<String> dp[], List<String> ans, 37 int end, List<String> temp){38 if(end <= 0){39 String strAns = temp.get(temp.size() - 1);40 for(int i = temp.size() - 2; i >= 0; i--)41 strAns += " " + temp.get(i);42 ans.add(strAns);43 return;44 }//if45 for(String str : dp[end]){46 temp.add(str);47 dfsStringList(dp, ans, end - str.length(), temp);48 temp.remove(temp.size() - 1);49 }50 }51 }
Word Break II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。