WordBreak2

题目地址：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"].

思路：
解决此题的关键在于用dfs来返回从某个起点开始的所有可行的解；用map是为了来memorize之前算过的解，可以大幅度减少运行时间；另外还有一些小技巧比如maxLen的使用来节省时间等。红色标记部分是memorization。


代码：

Map<Integer, List<String>> map = new HashMap<>();
public List<String> wordBreak(String s, List<String> wordDict) {
    List<String> rst = new ArrayList<>();
    if(s == null || s.length() == 0){
        return rst;
    }
    int maxLen = -1;
    for(String string : wordDict){
        maxLen = Math.max(maxLen, string.length());
    }
    return dfs(s, wordDict, 0, maxLen);
}

private List<String> dfs(String s, List<String> wordDict, int start, int maxLen){
    List<String> words = new ArrayList<>();
    if(start == s.length()){
        words.add("");
        return words;
    }
    for(int i = start + 1; i <= s.length() && i <= start + maxLen; i++){
        String temp = s.substring(start, i);
        if(wordDict.contains(temp)){
            List<String> ls;
            if(map.containsKey(i)){
                ls = map.get(i);
            }
            else{
                ls = dfs(s, wordDict, i, maxLen);
            }
            for(String string : ls){
                words.add(temp + (string.equals("") ? "" : " " + string));
            }
        }
    }
    map.put(start, words);
    return words;
}