140. Word Break II Leetcode Java

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:

Recursion:

Iteratively check s.substring(start,i), if dictionary contains this substring, recursively check if s.substring(i, end) can be break to the rest of words in the dictionary.

Need to take care of the first word, because all other words will be presented in the final result start with a whitespace except the first word.

Another tip is if the word is not breakable by calling the method of previous problem: Word Break, simply return an empty list rather than go through all the recursion steps.

 public List<String> wordBreak(String s, Set<String> dict) {  
    List<String> res=new ArrayList<String>();  
    if(s==null || !isBreakable(s,dict)) return res;  
    helper(s,0,new StringBuilder(),res,dict);  
    return res;  
   }  
   public void helper(String s, int start, StringBuilder items, List<String> res, Set<String> dict){  
     if(start>=s.length()){  
       res.add(items.toString());  
       return;  
     }  
     if(start!=0) items.append(" ");  
     for(int i=start;i<s.length();i++){  
       if(dict.contains(s.substring(start,i+1))){  
         items.append(s.substring(start,i+1));  
         helper(s,i+1,items,res,dict);  
         items.delete(items.length()+start-i-1,items.length());  
       }  
     }  
     if(start!=0) items.deleteCharAt(items.length()-1);  
   }  
   public boolean isBreakable(String s, Set<String> dict){  
     boolean[] res=new boolean[s.length()+1];  
     res[0]=true;  
     for(int i=0;i<s.length();i++){  
       for(int j=0;j<=i;j++){  
         if(res[j]&&dict.contains(s.substring(j,i+1))){  
           res[i+1]=true;  
           break;  
         }  
       }  
     }  
     return res[s.length()];  
   }