Given anon-emptystringsand a dictionarywordDictcontaining a list ofnon-emptywords, add spaces insto construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

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

UPDATE (2017/1/4):
ThewordDictparameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

tag: DFS

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> ans = new ArrayList<>();
        return dfs(s, new HashMap<String, List<String>>(), wordDict);
    }

    private List<String> dfs(String s, Map<String, List<String>> hash, List<String> wordDict){
        if (hash.containsKey(s)){
            return hash.get(s);
        }

        List<String> cur = new ArrayList<>();
        for (int i = 1; i <= s.length(); i++){
            String prefix = s.substring(0, i);

            if (wordDict.contains(prefix)){
                if (i == s.length()){
                    cur.add(s);
                }
                else{
                    List<String> postfixList = dfs(s.substring(i), hash, wordDict);
                    for (String postfix : postfixList){
                        cur.add(prefix + " " + postfix);
                    }
                }
            }
        }
        hash.put(s, cur);

        return cur;
    }
}