CONY的世界

140. Word Break II

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

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

這題用topdown 會比較漂亮，首先是base case 當input s 就在wordict 裡面的時候，把s 放如要return 的array list 裡面

接下來繼續判斷是不是還求他的組合，嘗試break down to subproblem，嘗試找個string t 在worddict 裡面，然後問題就可以被breakdown 成 wordbreak(s.substring(0,t))+t 

因為s.substring(0,t) 之後也可能被其他checking 用到，所以要減少computation，可以用個map 把 t 和它的wordarray 存起來，之後wordbreak call 的時候可以先找是不是已經算過了

如果沒有就自己做然後在存到map裡面

class Solution {
    HashMap<String, ArrayList<String>> map = new HashMap();
    
    public List<String> wordBreak(String s, List<String> wordDict) {
        return wordBreak(s, new HashSet<String>(wordDict), map);
    }
    public List<String> wordBreak(String s, HashSet<String> wordDict, HashMap<String, ArrayList<String>> map) {
        if(map.containsKey(s))
            return map.get(s);
        
         ArrayList<String> result = new ArrayList<String>();
        
        if(wordDict.contains(s))
            result.add(s);
        
        for(int index=0; index < s.length(); index++){
            String t=s.substring(index);
            if(wordDict.contains(t)) {
                for(String w : wordBreak(s.substring(0,index),wordDict, map))
                    result.add(w+" "+t);   
            }
        }
        map.put(s,result);
        return result;
    }
}