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

一刷：
用DFS + backtracking

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        List<String> res = new ArrayList<>();
        if(s == null || s.length() == 0) return res;
        List<String> cur = new ArrayList<>();
        Set<String> dict = new HashSet<>(wordDict);
        dfs(s, 0, cur, res, dict);
        return res;
    }
    
    private void dfs(String s, int pos, List<String> cur, List<String> res,
            Set<String> dict){
        if(pos == s.length()){
            String str = listToString(cur);
            res.add(str);
            return;
        }


        for(int i=pos; i<s.length(); i++){
            if(!dict.contains(s.substring(pos, i+1))) continue;
            cur.add(s.substring(pos, i+1));
            dfs(s, i+1, cur, res, dict);
            cur.remove(cur.size()-1);
        }
    }
    
    private String listToString(List<String> list){
        StringBuilder sb = new StringBuilder();
        //sb.append("\"");
        for(int i=0; i<list.size()-1; i++){
            sb.append(list.get(i));
            sb.append(" ");
        }
        sb.append(list.get(list.size()-1));
        //sb.append("\"");
        return sb.toString();
    }
}

但是在遇到
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
会出现超时的问题，因为有无数种排列组合。于是用dp来存储已经求得的解。这里的dp不是array而是Map<String, LinkedList<String>> map

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
       return dfs(s, new HashSet<String>(wordDict), new HashMap<String, LinkedList<String>>());
    }
    
   List<String> dfs(String s, Set<String> wordDict, HashMap<String, LinkedList<String>> map){
       if(map.containsKey(s))
           return map.get(s);
       
       LinkedList<String> res = new LinkedList<String>();
       if(s.length() == 0){
           res.add("");
           return res;
       }
       
       for(String word : wordDict){
           if(s.startsWith(word)){
               //remove the word length
               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;
   }
    
}

二刷
思路同上

public class Solution {
    public List<String> wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        Map<String, List<String>> cache = new HashMap<>();
        return dfs(s, cache, dict);
    }
    
    private List<String> dfs(String s, Map<String, List<String>> cache, Set<String> dict){
        if(cache.containsKey(s)) return cache.get(s);
        
        LinkedList<String> res = new LinkedList<>();
        if(s.length()==0){
            res.add("");
            return res;
        }
        
        for(String word : dict){
            if(s.startsWith(word)){
                List<String> sublist = dfs(s.substring(word.length()), cache, dict);
                for(String sub : sublist){
                    if(sub.isEmpty()){
                        res.add(word + sub);
                    }
                    else res.add(word + " " + sub);
                }
            }
        }
        cache.put(s, res);
        return res;
    }
}