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

Solution 1: first use DP to build up if [i...j] is in dict or not, then use DFS to collect all the possible breaks. The thing is to make judgement first, only if there is solution then dfs.

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> wordDict) {  
     char[] c=s.toCharArray();  
     int n=c.length;  
     boolean[][] dp=new boolean[n][n];  
     boolean[] exist=new boolean[n+1];  
     List<String> res=new ArrayList<>();  
     List<String> one=new ArrayList<>();  
     if (n==0) return res;  
     exist[0]=true;  
     for (int j=0; j<n; j++){  
       exist[j+1]=false;  
       for (int i=0; i<=j; i++) {  
         dp[i][j]=wordDict.contains(new String(c,i,j-i+1))?true:false;  
         if (dp[i][j] && exist[i]) exist[j+1]=true;  
       }  
     }  
     if (exist[n]) dfs(c,dp,0,one,res);  
     return res;  
   }  
   private void dfs(char[] c, boolean[][] dp, int d, List<String> one, List<String> res) {  
     if (d==c.length) {  
       StringBuilder sb=new StringBuilder();  
       for (String s:one) {  
         sb.append(s);  
         sb.append(' ');  
       }  
       res.add(sb.substring(0,sb.length()-1));  
     }  
     else {  
       for (int i=d; i<c.length; i++) {  
         if (dp[d][i]) {  
           one.add(new String(c,d,i-d+1));  
           dfs(c,dp,i+1,one,res);  
           one.remove(one.size()-1);  
         }  
       }  
     }  
   }  
 }