LeetCode程序员面试金典：单词拆分 II

　　题目：

　　给定一个字符串 s 用字符串字典worddict在字符串字典中添加空间来构建句子，使句子中的所有单词都在字典中。按任何顺序 返回所有这些可能的句子。

　　注：词典中的同一个单词可以在分段中多次重复使用。

　　示例 1：

　　输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]

　　输出:["cats and dog","cat sand dog"]

　　示例 2：

　　输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]

　　输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]

　　解释: 请注意，您可以重复使用字典中的单词。

　　示例3：

　　输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

　　输出:[]

　　代码实现：class Solution { public List wordBreak(String s, List wordDict) { Map>> map = new HashMap>>(); List> wordBreaks = backtrack(s, s.length(), new HashSet(wordDict), 0, map); List breakList = new LinkedList(); for (List wordBreak : wordBreaks) { breakList.add(String.join(" ", wordBreak)); } return breakList; } public List> backtrack(String s, int length, Set wordSet, int index, Map>> map) { if (!map.containsKey(index)) { List> wordBreaks = new LinkedList>(); if (index == length) { wordBreaks.add(new LinkedList()); } for (int i = index + 1; i <= length; i++) { String word = s.substring(index, i); if (wordSet.contains(word)) { List> nextWordBreaks = backtrack(s, length, wordSet, i, map); for (List nextWordBreak : nextWordBreaks) { LinkedList wordBreak = new LinkedList(nextWordBreak); wordBreak.offerFirst(word); wordBreaks.add(wordBreak); } } } map.put(index, wordBreaks); } return map.get(index); }}