WordBreakII.java

class WordBreakII {
    // 1. dfs with memo
    private Map<String, List<String>> memo;
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>();
        Set<String> set = new HashSet<>(wordDict);
        memo = new HashMap<>();
        
        return wordBreak(s, set);
    }
    
    private List<String> wordBreak(String s, Set<String> set) {
        if (memo.containsKey(s)) return memo.get(s);
        
        List<String> ans = new ArrayList<>();
        if (set.contains(s)) ans.add(s);
        
        for (int j = 1; j < s.length(); j++) {
            String right = s.substring(j);
            if (!set.contains(right)) continue;
            
            String left = s.substring(0, j);
            List<String> one = concatAns(wordBreak(left, set), right);
            ans.addAll(one);
        }
        
        memo.put(s, ans);
        return ans;
    }
    
    private List<String> concatAns(List<String> cur, String right) {
        List<String> ans = new ArrayList<>();
        for (String prefix : cur) {
            ans.add(prefix + " " + right);
        }
        return ans;
    }
  
    // 2. dfs, TLE
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>();
        Set<String> set = new HashSet<>(wordDict);
        List<String> cur = new ArrayList<>();
        memo = new HashMap<>();
        dfs(s, 0, set, cur, ans);
        return ans;
    }
    
    private void dfs(String s, Set<String> set, List<String> cur, List<String> ans) {
        if (start == s.length()) {
            ans.add(getStringFromList(cur));
            return;
        }
        
        for (int j = start + 1; j <= s.length(); j++) {
            String sub = s.substring(start, j);
            if (!set.contains(sub)) continue;
            cur.add(sub);
            dfs(s, j, set, cur, ans);   
            cur.remove(cur.size() - 1);
        }
        return false;
    }
    
    private String getStringFromList(List<String> cur) {
        StringBuilder sb = new StringBuilder();
        for (String s : cur) sb.append(s + " ");
        return sb.toString().trim();
    }
}