My code:

public class Solution {
    public List<String> wordBreak(String s, Set<String> wordDict) {
        return helper(s, new HashMap<String, List<String>>(), wordDict);
    }
    
    private List<String> helper(String s, Map<String, List<String>> map, Set<String> wordDict) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        List<String> list = new LinkedList<String>();
        if (s.length() == 0) {
            list.add("");
            return list;
        }
        
        for (String word : wordDict) {
            if (s.startsWith(word)) {
                List<String> ret = helper(s.substring(word.length()), map, wordDict);
                for (String part : ret) {
                    list.add(word + (part.length() == 0 ? "" : " ") + part);
                }
            }
        }
        
        map.put(s, list);
        return list;
    }
}

看了答案写出来的。

其实思路很简单。就是dfs + memory cache
reference:
https://discuss.leetcode.com/topic/27855/my-concise-java-solution-based-on-memorized-dfs/3

time complexity:
O(len(wordDict) ^ len(s / minWordLenInDict))

然后 BFS的做法不知道怎么做。

Anyway, Good luck, Richardo! -- 09/06/2016