July - Day 30 - Word Break II

Solution.java

// https://leetcode.com/explore/challenge/card/july-leetcoding-challenge/548/week-5-july-29th-july-31st/3406/

import java.util.*;

class Solution {
  public List<String> wordBreak(String s, List<String> dict) {
        HashMap<String, ArrayList<String>> dp = new HashMap<String, ArrayList<String>>();
        return dfs(s, new HashSet(dict), dp);
    }
    ArrayList<String> dfs(String s, Set<String> dict, HashMap<String, ArrayList<String>> dp)
    {
        if(dp.containsKey(s))
            return dp.get(s);
            
        ArrayList<String> result = new ArrayList<String>();
        
        for(int i = 0; i < s.length(); ++i)
        {
            if(dict.contains(s.substring(0, i + 1)))
            {
                if(i == s.length() - 1)
                    result.add(s);
                else
                {
                    ArrayList<String> t = dfs(s.substring(i + 1), dict, dp);
                    if(t.size() > 0)
                        for(String iter : t)
                            result.add(s.substring(0, i + 1) + " " + iter);
                }
            }
        }
        dp.put(s, result);
        return result;
    }   
}