[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）。

 public class Solution {

     public List<String> wordBreak(String s, Set<String> dict) {

         List<String> result=new ArrayList<String>();

         if(!wordBreakPossible(s,dict)) return result;

         dfs(s,dict,result,"",0);

         return result;

     }

     private void dfs(String s, Set<String> dict, List<String> result,String temp, int start) {

         // TODO Auto-generated method stub

         if(start==s.length())

             result.add(temp);

         else{

             if(start!=0)

                 temp+=" ";

             for(int i=start;i<s.length();i++){

                 String word=s.substring(start, i+1);

                 if(dict.contains(word))

                     dfs(s,dict,result,temp+word,i+1);

             }

         }

     }

     private boolean wordBreakPossible(String s, Set<String> dict) {

         // TODO Auto-generated method stub

         boolean[] state=new boolean[s.length()+1];

         state[0]=true;

         for(int i=1;i<=s.length();i++){

             for(int j=i-1;j>=0;j--){

                 if(state[j]&&dict.contains(s.substring(j, i))){

                     state[i]=true;

                     break;

                 }

             }

         }

         return state[s.length()];

     }

 }

----------------------------------------------------------------------

20150221:

又忘了在dfs之前去判断这个string是否可以被这个dictionary分割：

导致出现了TLE:

Last executed input:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", ["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]

 public class Solution {

     public List<String> wordBreak(String s, Set<String> dict) {

         List<String> res=new ArrayList<String>();

         if(s==null||s.length()==0||dict==null||dict.size()==0)

             return res;

         if(!wordBreakPossible(s,dict)) return res;

         dfs(res,s,dict,"");

         return res;

     }

     public void dfs(List<String> res,String s,Set<String> dict,String temp){

         if(s.length()==0){

             res.add(temp.trim());

             return;

         }

         for(int i=1;i<=s.length();++i){

             String t=s.substring(0,i);

             if(dict.contains(t)){

                 dfs(res,s.substring(i),dict,temp+" "+t);

             }else{

                 continue;

             }

         }

     }

     private boolean wordBreakPossible(String s, Set<String> dict) {

         // TODO Auto-generated method stub

         boolean[] state=new boolean[s.length()+1];

         state[0]=true;

         for(int i=1;i<=s.length();i++){

             for(int j=i-1;j>=0;j--){

                 if(state[j]&&dict.contains(s.substring(j, i))){

                     state[i]=true;

                     break;

                 }

             }

         }

         return state[s.length()];

     }

 }

巴特西

[Leetcode] Word BreakII

最新文章

热门文章