题目
给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
注意：词典中的同一个单词可能在分段中被重复使用多次。
示例 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"] 输出:[]
解题
方法一：哈希集合+dfs
class Solution { public: vector<string> res; unordered_set<string> set; void dfs(string& s,int startIndex,string&& path){ if(startIndex==s.size()){ res.push_back(path); return; }else if(startIndex!=0) path+=" ";//头部和尾部不用加空格 for(int i=startIndex;i<s.size();i++){ string tmp=s.substr(startIndex,i-startIndex+1); if(set.count(tmp)){ dfs(s,i+1,path+tmp);//以形参方式带入，就不需要手动回溯了 } } } vector<string> wordBreak(string s, vector<string>& wordDict) { set=unordered_set<string>(wordDict.begin(),wordDict.end()); dfs(s,0,""); return res; } };
方法二：字典树+dfs
class Trie{ public: bool isEnd=false; vector<Trie*> next=vector<Trie*>(26,nullptr); }; class Solution { public: Trie* trie=new Trie(); vector<string> res; vector<string> wordBreak(string s, vector<string>& wordDict) { for(string& word:wordDict){ insert(word); } dfs(s,0,""); return res; } void dfs(string& word,int startIndex,string&& path){ if(startIndex==word.size()){ res.push_back(path); return; }else if(startIndex!=0) path+=" "; Trie* node=trie; string tmp=""; for(int i=startIndex;i<word.size();i++){ char c=word[i]; tmp+=c; if(node->next[c-'a']) node=node->next[c-'a']; else return; if(node->isEnd){ dfs(word,i+1,path+tmp); } } } void insert(string& word){ Trie* node=trie; for(char c:word){ if(node->next[c-'a']==nullptr){ node->next[c-'a']=new Trie(); } node=node->next[c-'a']; } node->isEnd=true; } };
