Word Break II

Source

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

Java

public class Solution {
    public ArrayList<String> wordBreak(String s, Set<String> dict) {
        Map<String, ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        return wordBreakHelper(s,dict,map);
    }

    public ArrayList<String> wordBreakHelper(String s, Set<String> dict, Map<String, ArrayList<String>> map){
        if(map.containsKey(s)) return map.get(s);
        ArrayList<String> result = new ArrayList<String>();
        int n = s.length();
        for(int i = 1; i <= n; ++i){
            String left = s.substring(0,i);

            if(dict.contains(left)){
                if(i == n){
                    result.add(left);
                }else{
                    String right = s.substring(i);
                    ArrayList<String> tmp = wordBreakHelper(right, dict, map);
                    for(String item:tmp){
                        item = left + " " + item;
                        result.add(item);
                    }
                }
            }
        }
        map.put(s, result);
        return result;
    }
}