首页 > 代码库 > [Leetcode] Word BreakII
[Leetcode] Word BreakII
Question:
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"]
.
----------------------------------------------
Solution:
dfs.
但是需要注意的是,在dfs之前,需要判断这个string能不能被这个dictionary分割(Word Break)。
1 public class Solution { 2 public List<String> wordBreak(String s, Set<String> dict) { 3 List<String> result=new ArrayList<String>(); 4 if(!wordBreakPossible(s,dict)) return result; 5 dfs(s,dict,result,"",0); 6 return result; 7 } 8 9 private void dfs(String s, Set<String> dict, List<String> result,String temp, int start) { 10 // TODO Auto-generated method stub 11 if(start==s.length()) 12 result.add(temp); 13 else{ 14 if(start!=0) 15 temp+=" "; 16 for(int i=start;i<s.length();i++){ 17 String word=s.substring(start, i+1); 18 if(dict.contains(word)) 19 dfs(s,dict,result,temp+word,i+1); 20 } 21 } 22 } 23 24 private boolean wordBreakPossible(String s, Set<String> dict) { 25 // TODO Auto-generated method stub 26 boolean[] state=new boolean[s.length()+1]; 27 state[0]=true; 28 for(int i=1;i<=s.length();i++){ 29 for(int j=i-1;j>=0;j--){ 30 if(state[j]&&dict.contains(s.substring(j, i))){ 31 state[i]=true; 32 break; 33 } 34 35 } 36 } 37 return state[s.length()]; 38 } 39 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。