[LeetCode] Word Break II

Problem:

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:O(n*n)

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        Map<String, ArrayList<String>> map = new HashMap<>();
        return wordBreakHelper(s,dict,map);
    }
   
    public ArrayList<String> wordBreakHelper(String s, Set<String> dict, Map<String, ArrayList<String>> map){
        if(map.get(s)!=null) 
            return map.get(s);
        ArrayList<String> result = new ArrayList<>();
        if(s == null || s.length() == 0) 
            return result;
        for(int len = 1; len <= s.length(); len++){
            String prefix = s.substring(0,len);
            if(dict.contains(prefix)){
                if(len == s.length()){
                    result.add(prefix);
                }else{
                    String subfix = s.substring(len);
                    ArrayList<String> tmp = wordBreakHelper(subfix, dict, map);
                    for(String item:tmp){
                        item = prefix + " " + item;
                        result.add(item);
                    }
                }  
            }
        }
        map.put(s, result);
        return result;
    }
}