Word Break II

https://leetcode.com/problems/word-break-ii/description/

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to 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"].

解题：给定一个string和词典，要求按照词典break string，返回所有组合。我们用一个hashmap来存string和对应的结果，每次我们遍历词典，如果找到当前string的prefix，我们切掉当前词，然后继续DFS。过程见下图。map可以用于减去重复的词的枝，比如dog。

                catsanddog
                /        \
               cat       cats   剪掉prefix
             sanddog    anddog  剩下
              /           \
            sand           and   剪掉prefix
            dog            dog   剩下
            /                \
          dog                dog   剪掉prefix
          “”                  “”   剩下
          /                    \
         ""                    ""

class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        return DFS(s, wordDict, new HashMap<String, LinkedList<String>>());
    }

    List<String> DFS(String s, List<String> wordDict, HashMap<String, LinkedList<String>> map) {
        //if the s is in map, directly return
        if (map.containsKey(s)) {
            return map.get(s);
        }

        LinkedList<String> res = new LinkedList<String>();
        if (s.length() == 0) {
            res.add("");
            return res;
        }

        //each word in wordDict, if s has the prefix, cut the prefix, do DFS
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> sublist = DFS(s.substring(word.length()), wordDict, map);
                for (String sub : sublist) {
                    res.add(word + (sub.isEmpty() ? "" : " ") + sub);
                }
            }
        }
        map.put(s, res);
        return res;
    }
}