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

Solution: 取不同长度的前缀，如果前缀在词典中，则把后缀递归。用hashmap记录每个子串的结果，避免重复搜索

    public List<String> wordBreak(String s, Set<String> wordDict) {
        if(s == null || s.length() == 0 || wordDict == null || wordDict.size() == 0){
            return new ArrayList<String>();
        }
        return helper(s, new HashMap<String, List<String>>(), wordDict);

    }
    private List<String> helper(String s, HashMap<String, List<String>> hashmap, Set<String> dict){
        if(hashmap.containsKey(s)){
            return hashmap.get(s);
        }
        List<String> ans = new ArrayList<String>();
        if(s == null || s.length() == 0){
            return ans;
        }
        for(int i = 1; i <= s.length(); i++){
            String prefix = s.substring(0, i);
            if(dict.contains(prefix)){
                if(prefix.length() == s.length()){
                    ans.add(prefix);
                } else{
                    String suffix = s.substring(i);
                    List<String> temp = helper(suffix, hashmap, dict);
                    for(String item : temp){
                        ans.add(prefix + " " + item);
                    }
                }
            }
        }
        hashmap.put(s, ans);
        return ans;
    }