给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
示例 1：
输入：words =
[“cat”,“cats”,“catsdogcats”,“dog”,“dogcatsdog”,“hippopotamuses”,“rat”,“ratcatdogcat”]
输出：[“catsdogcats”,“dogcatsdog”,“ratcatdogcat”]
示例 2：
输入：words = [“cat”,“dog”,“catdog”]
输出：[“catdog”]
提示：
1 <= words.length <= 1e4
0 <= words[i].length <= 30
words[i] 仅由小写字母组成
0 <= sum(words[i].length) <= 1e5
字典树的模板题，先根据words构建字典树，然后dfs每个words[i]，判断它是否是一个连接词。
具体到dfs的过程就很简单了，我们从开头位置出发看从该结点到当前搜索单词的末尾的拼接情况，首先一直往下搜索到末尾，这里是确保有以该字母开头的前缀。在不断返回上级的时候遇到了isend为真的情况，就说明字符串中存在从头结点到该结点的路径所代表的字符串，我们从头结点，当前的start开始更换结点搜索，这代表着更换到另一个前缀上去。最后我们判断返回值是否大于1，如果是就说明该字符串是一个拼接词。
class Solution {
struct TrieNode{
bool isend;
TrieNode* next[26];
TrieNode(){
isend=false;
memset(next,false,sizeof(next));
}
};
struct Trie{
TrieNode* root;
Trie() {
root=new TrieNode();
}
void insert(const string & s){
TrieNode* cur=root;
for(int i=0;i<s.size();++i){
if(!cur->next[s[i]-'a']){
cur->next[s[i]-'a']=new TrieNode();
}
cur=cur->next[s[i]-'a'];
}
cur->isend=true;
}
int dfs(TrieNode* cur,const string &s,int start){
if(!cur){
return 0;
}
if(start==s.size()){
return cur->isend;
}
int ans=0;
ans+=dfs(cur->next[s[start]-'a'],s,start+1);
if(ans>1){
return 2;
}
if(cur->isend){
ans+=dfs(root,s,start);
}
return ans>1?2:ans;
}
};
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
Trie t;
for(int i=0;i<words.size();++i){
t.insert(words[i]);
}
vector<string> ans;
for(int i=0;i<words.size();++i){
if(t.dfs(t.root,words[i],0)>1){
ans.push_back(words[i]);
}
}
return ans;
}
};
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： [“cat”,“banana”,“dog”,“nana”,“walk”,“walker”,“dogwalker”]
输出： “dogwalker”
提示：
0 <= len(words) <= 200
1 <= len(words[i]) <= 100
跟上一题简直一模一样，不过区别就是我们确定答案字符串要判断字典序和长度。
class Solution {
struct TrieNode{
bool isend;
TrieNode* next[26];
TrieNode(){
isend=false;
memset(next,false,sizeof(next));
}
};
struct Trie{
TrieNode* root;
Trie() {
root=new TrieNode();
}
void insert(const string & s){
TrieNode* cur=root;
for(int i=0;i<s.size();++i){
if(!cur->next[s[i]-'a']){
cur->next[s[i]-'a']=new TrieNode();
}
cur=cur->next[s[i]-'a'];
}
cur->isend=true;
}
int dfs(TrieNode* cur,const string &s,int start){
if(!cur){
return 0;
}
if(start==s.size()){
return cur->isend;
}
int ans=0;
ans+=dfs(cur->next[s[start]-'a'],s,start+1);
if(ans>1){
return 2;
}
if(cur->isend){
ans+=dfs(root,s,start);
}
return ans>1?2:ans;
}
};
public:
string longestWord(vector<string>& words) {
Trie t;
for(int i=0;i<words.size();++i){
t.insert(words[i]);
}
string ans="";
for(int i=0;i<words.size();++i){
if(t.dfs(t.root,words[i],0)>1){
ans=ans.size()>words[i].size()||
(words[i].size()==ans.size()&&ans<words[i])?ans:words[i];
}
}
return ans;
}
};