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

 

// DFSpublic class Solution {    public ArrayList
     
       wordBreak(String s, Set
      
        dict) {        ArrayList
       
         result = new ArrayList
        
         ();        if(s == null || s.length() == 0)            return result;                int len = s.length();        boolean[] dp = new boolean[len+1];        dp[0] = true;        for(int i = 0; i< len ; i++){            if(!dp[i])                continue;                        for(String e : dict){                int end = i+ e.length();                if(end > len)                    continue;                String sub = s.substring(i, end);                if(dict.contains(sub))                    dp[end]  = true;            }        }                if(dp[len] == false) return result;        StringBuilder  sb = new StringBuilder();        dfs(0, sb, s, dict, result);        return result;    }        private void dfs(int start, StringBuilder sb, String s, Set
         
           dict, ArrayList
          
            result){ int len = s.length(); if(start >= len){ result.add(new String(sb)); return; } for(int i = start+1; i<= len; i++){ String sub = s.substring(start, i); if(dict.contains(sub)){ int oldLen = sb.length(); if(oldLen != 0){ sb.append(" "); } sb.append(sub); dfs(i, sb, s, dict, result); sb.delete(oldLen, sb.length()); } } }}
          
         
        
       
      
     

 

 

 

DP + Backtrack

// DP + back track    public ArrayList
     
       wordBreak2(String s, Set
      
        dict) {        int n = s.length();        ArrayList
       
        
         > pres = new ArrayList
         
          
           >( n); // initialize for (int i = 0; i < n; ++i) pres.add(new ArrayList
           
            ()); // DP. pres[i] stores position j where should insert space for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { String suffix = s.substring(j, i + 1); if ((j == 0 || pres.get(j - 1).size() > 0) && dict.contains(suffix)) pres.get(i).add(j); } } return getPath(s, n, pres); } public ArrayList
            
              getPath(String s, int n, ArrayList
             
              
               > pres) { ArrayList
               
                 res = new ArrayList
                
                 (); for (int pre : pres.get(n - 1)) { if (pre == 0) { res.add(s.substring(0, n)); } else { ArrayList
                 
                   preres = getPath(s, pre, pres); String sub = s.substring(pre, n); for (String ss : preres) res.add(ss + " " + sub); } } return res; }