Word Break II (LeetCode Dynamic Programming)

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

Idea: Depth-first search with recursive dynamic programming. At each position of the input string s, break it to two halves, if the prefix is contained in the dict, recursively break the suffix to words. Use a hashmap to cache the broken strings computed before.

Time: O(n^2) Space: O(n^2)

Code:

 public class Solution {  
   public List<String> wordBreak(String s, Set<String> dict) {  
     HashMap<String,List<String>> map=new HashMap<String,List<String>>();  
     return dfs(s,dict,map);  
   }  
   public List<String> dfs(String s, Set<String> dict, HashMap<String,List<String>> map)  
   {  
     if(map.containsKey(s))  
       return map.get(s);  
     List<String> result=new ArrayList<String>();  
     int n=s.length();  
     if(n<=0)  
     {  
       map.put(s,result);  
       return result;  
     }  
     for(int i=1;i<=s.length();i++)  
     {  
       String prefix=s.substring(0,i);  
       if(dict.contains(prefix))  
       {  
         if(prefix.length()==s.length())  
           result.add(prefix);  
         else  
         {  
           String suffix=s.substring(i);  
           List<String> breakSuffix=dfs(suffix,dict,map);  
           for(String tmp:breakSuffix)  
             result.add(prefix+" "+tmp);  
         }  
       }  
     }  
     map.put(s,result);  
     return result;  
   }  
 }