Word Break ... ||

When you have one, you must have two! Instead, this one uses a recursion. HashMap is always an amazing data structure. This one uses the map to store temporary strings and corresponding arrays, and thus reduces number of recursions.

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

Take the "catsanddog" as the example.
When the iteration detects "cat", it splits the string to prefix ="cat" and suffix = "sanddog". Take the suffix as the input, the method checks for the next prefix ("sand"). When it detects "dog", the input is in the dictionary, so we simply add the input into the result array (rst) and return.

"catsanddog" -> len == 3, "cat" + "sanddog" -> "sand" + "dog" -> "dog", add to the map and rst, return rst -> "sand" + " " +  "dog" (from tmp), add to the map and rst, return rst -> "cat" + " " + "sand dog" = "cat sand dog", add to the map and rst;
"catsanddog" -> len == 4, "cats" + "anddog" -> "and" + "dog" -> "dog", get from map, return rst -> "and" + " " + "dog" -> "cats" + " " + "and dog" = "cats and dog", add to the map and rst, return rst;
                    

public class Solution {
    public ArrayList wordBreak(String s, Set dict) {
        ArrayList rst = new ArrayList ();
        if (s == null || dict.isEmpty())
            return rst;
        HashMap> map = new HashMap>();
        rst = wordBreakHelper(s, dict, map);
        return rst;
        
    }
    private ArrayList wordBreakHelper(String s, Set dict, HashMap> map)
    {
        if (map.containsKey(s))
            return map.get(s);
        ArrayList rst = new ArrayList();
        int length = s.length();
        if (length <= 0)
            return rst;
        for (int len = 1; len <= length; len++)
        {
            String prefix = s.substring(0, len);
            if (dict.contains(prefix))
            {
                if (len == length)
                    rst.add(prefix);
                else
                {
                    String suffix = s.substring(len);
                    ArrayList tmp = wordBreakHelper(suffix, dict, map);
                    for (String items : tmp)
                    {
                        String words = prefix + " " + items;
                        rst.add(words);
                    }
                }
            }
        }
        map.put(s, rst);
        return rst;
    }
}