题目
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。
示例 1：
输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"] 输出：["catsdogcats","dogcatsdog","ratcatdogcat"] 解释："catsdogcats" 由 "cats", "dog" 和 "cats" 组成; "dogcatsdog" 由 "dog", "cats" 和 "dog" 组成; "ratcatdogcat" 由 "rat", "cat", "dog" 和 "cat" 组成。
示例 2：
输入：words = ["cat","dog","catdog"] 输出：["catdog"]
解题
方法一：字典树+深度优先搜索
//定义字典树 class Trie{ public: bool isEnd; vector<Trie*> next; Trie(){ this->isEnd=false; this->next=vector<Trie*>(26,nullptr); }; }; class Solution { public: Trie* trie=new Trie(); vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { vector<string> res; //排序，保证字数少的在前面 sort(words.begin(), words.end(), [](string& a,string& b){ return a.size() < b.size(); }); //遍历words，如果是连接词就加入res，否则加入字典树 for(string& word:words){ if(word.size()==0) continue; if(dfs(word,0)){//深度优先，递归判断是否为连接词 res.push_back(word);//加入结果 } else insert(word);//插入字典树 } return res; } bool dfs(string& word,int startIndex){ if(startIndex==word.size()) return true; Trie* node=trie; for(int i=startIndex;i<word.size();i++){ char c=word[i]; node=node->next[c-'a']; if(node==nullptr) return false; if(node->isEnd){ if(dfs(word,i+1)) return true; } } return false; } //插入字典树 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; } };
