給定一個非空字符串 s 和一個包含非空單詞列表的字典 wordDict，在字符串中增加空格來構建一個句子，使得句子中所有的單詞都在詞典中。返回所有這些可能的句子。

說明：

分隔時可以重復使用字典中的單詞。
你可以假設字典中沒有重復的單詞。
示例 1：

輸入:
s = “catsanddog”
wordDict = [“cat”, “cats”, “and”, “sand”, “dog”]
輸出:
[
“cats and dog”,
“cat sand dog”
]

代碼

class Solution {Map<Integer,List<List<String>>> listMap=new HashMap<>();public List<String> wordBreak(String s, List<String> wordDict) {Trie trie=new Trie();Set<Integer> set=new HashSet<>();for(String c:wordDict) {set.add(c.length());trie.insert(c);}List<String> ret=new ArrayList<>(); List<List<String>> resss=awordBreak(s,0,trie,set);for(java.util.List<String> list:resss) ret.add(String.join(" ",list));//添加空格return ret;}public List<List<String>> awordBreak(String s, int loc,Trie trie,Set<Integer> set) {if(!listMap.containsKey(loc)){List<List<String>> temp=new LinkedList<List<String>>();if(loc==s.length())temp.add(new ArrayList<>());for(int c:set)//測試字典的所有單詞{if(loc+c<=s.length()){String need=s.substring(loc,loc+c);if(trie.search(need)){//該單詞合法List<List<String>> nexts=   awordBreak(s,loc+c,trie,set);//遞歸獲取字符串后部分返回的單詞序列for(List<String> list:nexts)//將不同的單詞序列與當前單詞連接{LinkedList<String> next=new LinkedList<>(list);next.offerFirst(need);temp.add(next);}}}}listMap.put(loc,temp);}return listMap.get(loc);}class TrieNode {//字典樹private TrieNode[] links;private final int  r=26;private boolean isEnd;public TrieNode() {this.links = new TrieNode[r];}public boolean contains(char c) {return links[c-'a']!=null;}public void put(char c,TrieNode node) {links[c-'a']=node;}public TrieNode get(char c) {return links[c-'a'];}public boolean isEnd() {return isEnd;}public void setEnd() {isEnd = true;}}class  Trie{private TrieNode root;public Trie() {this.root = new TrieNode();}public void insert(String s){TrieNode cur=root;for(int i=0;i<s.length();i++){if(!cur.contains(s.charAt(i))){cur.put(s.charAt(i),new TrieNode());}cur=cur.get(s.charAt(i));}cur.setEnd();}public boolean search(String s){TrieNode cur=root;for(int i=0;i<s.length();i++){if(cur.contains(s.charAt(i))){cur=cur.get(s.charAt(i));}else return false;}return cur.isEnd;}}
}