Word Break II

Java

public class Solution {
    /*
     * @param s: A string
     * @param wordDict: A set of words.
     * @return: All possible sentences.
     */
    public List<String> wordBreak(String s, Set<String> wordDict) {
        // write your code here
        Map<String, List<String>> memo = new HashMap<>();
        memo.put("", new ArrayList<>());
        memo.get("").add("");
        
        return dfs(s, wordDict, memo);
    }
    
    private List<String> dfs(String s, Set<String> dict, Map<String, List<String>> memo) {
        if (memo.containsKey(s)) {
            return memo.get(s);
        }
        
        List<String> ans = new ArrayList<>();
        
        for (int i = 1; i <= s.length(); i++) {
            String s1 = s.substring(0, i);
            String s2 = s.substring(i);
            
            if (dict.contains(s1)) {
                List<String> s2_res = dfs(s2, dict, memo);
                for (String item : s2_res) {
                    if (item == "") {
                        ans.add(s1);
                    } else {
                        ans.add(s1 + " " + item);
                    }
                }
            }
        }
        memo.put(s, ans);
        return ans;
    }
}