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”]

---

和word break I 差不多的思路，第一遍TLE, 原因是对于任何一个i，如果i+1到s.length()这一段是not solvable，那么0-i这一段不需要进行。因此在解决问题之前，做一遍word break I， 用于判断有没有必要对当前i找出list of strings.

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new ArrayList<String>();
        if (s == null || dict == null || s.length() == 0 || dict.size() == 0) {
            return result;
        }
        boolean[] solvable = new boolean[s.length() + 1];
        solvable[s.length()] = true;
        for (int i = s.length()-1; i >= 0; i--) {//
            for (int j = s.length() - 1; j >= i; j--) {
                if (solvable[j+1] == true && dict.contains(s.substring(i, j+1))) {
                    solvable[i] = true;
                    break;
                }
            }
        }
        
        Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        for (int i = 0; i < s.length(); i++) {
            if(i == s.length()-1 || solvable[i+1]) {
                for (int j = 0; j <= i; j++) {
                    if ((j == 0 || map.containsKey(j-1)) && dict.contains(s.substring(j, i+1))) {
                        if (j == 0) {
                            List<String> newList = new ArrayList<String>();
                            newList.add(s.substring(0, i+1));
                            map.put(i, newList);
                        } else {
                            List<String> curList = map.containsKey(i) ? map.get(i) : new ArrayList<String>();
                            List<String> jList = map.get(j-1);
                            for (String str : jList) {
                                curList.add(str + " " + s.substring(j, i+1));
                            }
                            map.put(i, curList);
                        }
                    }
                }
            }
        }
        return map.get(s.length()-1) == null ? result : map.get(s.length()-1);
    }
}