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

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        ArrayList<String> ret = new ArrayList<String>();
        if(s==null || s.length()==0) {
            return ret;
        }
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        map.put(-1, new ArrayList<Integer>());
        for(int i=0;i<s.length();i++) {
            String sub = s.substring(0, i+1);
            for(int j=-1;j<i;j++) {
                if(map.containsKey(j) && dict.contains(s.substring(j+1, i+1))) {
                    insert(map, i, j);
                }
            }
        }
       
        if (map.containsKey(s.length()-1)) {
            recursive(map, ret, "", s.length()-1, s);
            return ret;
        } else {
            return ret;
        }
    }
    
    private void recursive(HashMap<Integer, ArrayList<Integer>> map, ArrayList<String> ret, String s, int end, String orig) {
        ArrayList<Integer> lst = map.get(end);
        for(int i : lst) {
            String newS = orig.substring(i+1, end+1) + " " + s;
            if(i==-1) {
                ret.add(newS.trim());
            } else {
                recursive(map, ret, newS, i, orig);
            }
        }
    }
    
    private void insert(HashMap<Integer, ArrayList<Integer>> map, int key, int val) {
        ArrayList<Integer> vals = map.get(key);
        if(vals==null) {
            vals = new ArrayList<Integer>();
            map.put(key, vals);
        }
        vals.add(val);
    }
}

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> ret = new ArrayList<String>();
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        map.put(0, new ArrayList<Integer>());
        for(int i=1;i<=s.length();i++) {
            ArrayList<Integer> idxes = new ArrayList<Integer>();
            for(int j=i;j>=0;j--) {
                if(!map.containsKey(j)) continue;
                String sub = s.substring(j, i);
                if(dict.contains(sub)) {
                    idxes.add(j);
                }
            }   
            if(idxes.size()!=0) map.put(i, idxes);
        }
        if(map.containsKey(s.length())) {
            helper(map, ret, new ArrayList<String>(), s.length(), s);
            return ret;
        } else {
            return ret;
        }
    }
   
    private void helper(HashMap<Integer, ArrayList<Integer>> map, List<String> ret, List<String> cur, int idx, String s) {
        if(idx==0) {
            StringBuilder sb = new StringBuilder();
            for(int i=cur.size()-1;i>=0;i--) {
                sb.append(cur.get(i)).append(" ");
            }
            ret.add(sb.toString().trim());
        } else {
            ArrayList<Integer> previousIdxes = map.get(idx);
            for(int previousIdx : previousIdxes) {
                cur.add(s.substring(previousIdx, idx));
                helper(map, ret, cur, previousIdx, s);
                cur.remove(cur.size()-1);
            }
        }
    }
}