LeetCode力扣官方题解472。连接词

　　题目描述
　　给你一个不含重复单词的字符串数组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〕
　　提示：1words。length100words〔i〕。length1000words〔i〕仅由小写字母组成0sum（words〔i〕。length）10
　　解决方案
　　前言
　　本文的解法需要使用字典树。如果读者对字典树不了解，建议首先阅读208。实现Trie（前缀树）的官方题解，在理解字典树的实现之后继续阅读本文。
　　方法一：字典树记忆化搜索
　　思路与算法
　　判断一个单词是不是连接词，需要判断这个单词是否完全由至少两个给定数组中的更短的非空单词（可以重复）组成。判断更短的单词是否在给定数组中，可以使用字典树实现。
　　为了方便处理，首先将数组words按照字符串的长度递增的顺序排序，排序后可以确保当遍历到任意单词时，比该单词短的单词一定都已经遍历过，因此可以根据已经遍历过的全部单词判断当前单词是不是连接词。
　　在将数组words排序之后，遍历数组，跳过空字符串，对于每个非空单词，判断该单词是不是连接词，如果是连接词则将该单词加入结果数组，如果不是连接词则将该单词加入字典树。
　　判断一个单词是不是连接词的做法是在字典树中搜索。从该单词的第一个字符（即下标0处的字符）开始，在字典树中依次搜索每个字符对应的结点，可能有以下几种情况：如果一个字符对应的结点是单词的结尾，则找到了一个更短的单词，从该字符的后一个字符开始搜索下一个更短的单词；如果一个字符对应的结点在字典树中不存在，则当前的搜索结果失败，回到上一个单词的结尾继续搜索。
　　如果找到一个更短的单词且这个更短的单词的最后一个字符是当前单词的最后一个字符，则当前单词是连接词。由于数组words中没有重复的单词，因此在判断一个单词是不是连接词时，该单词一定没有加入字典树，由此可以确保判断连接词的条件成立。
　　由于一个连接词由多个更短的非空单词组成，如果存在一个较长的连接词的组成部分之一是一个较短的连接词，则一定可以将这个较短的连接词换成多个更短的非空单词，因此不需要将连接词加入字典树。
　　为了降低时间复杂度，需要使用记忆化搜索。对于每个单词，创建与单词相同长度的数组记录该单词的每一个下标是否被访问过，然后进行记忆化搜索。搜索过程中，如果一个下标已经被访问过，则从该下标到末尾的部分一定不是由给定数组中的一个或多个非空单词组成（否则上次访问时已经可以知道当前单词是连接词），只有尚未访问过的下标才需要进行搜索。
　　代码
　　Python3classTrie：definit（self）：self。children〔None〕26self。isEndFalsedefinsert（self，word：str）：nodeselfforchinword：chord（ch）ord（a）ifnotnode。children〔ch〕：node。children〔ch〕Trie（）nodenode。children〔ch〕node。isEndTruedefdfs（self，word：str，start：int，vis：List〔bool〕）bool：ifstartlen（word）：returnTrueifvis〔start〕：returnFalsevis〔start〕Truenodeselfforiinrange（start，len（word））：nodenode。children〔ord（word〔i〕）ord（a）〕ifnodeisNone：returnFalseifnode。isEndandself。dfs（word，i1，vis）：returnTruereturnFalseclassSolution：deffindAllConcatenatedWordsInADict（self，words：List〔str〕）List〔str〕：words。sort（keylen）ans〔〕rootTrie（）forwordinwords：ifword：continueifroot。dfs（word，0，〔False〕len（word））：ans。append（word）else：root。insert（word）returnans
　　CstructTrie｛boolisEnd；vectorTriechildren；Trie（）｛thischildrenvectorTrie（26，nullptr）；thisisEndfalse；｝｝；classSolution｛public：TrietrienewTrie（）；vectorstringfindAllConcatenatedWordsInADict（vectorstringwords）｛vectorstringans；sort（words。begin（），words。end（），〔〕（conststringa，conststringb）｛returna。size（）b。size（）；｝）；for（inti0；iwords。size（）；i）｛stringwordwords〔i〕；if（word。size（）0）｛continue；｝vectorintvisited（word。size（），0）；if（dfs（word，0，visited））｛ans。emplaceback（word）；｝else｛insert（word）；｝｝returnans；｝booldfs（conststringword，intstart，vectorintvisited）｛if（word。size（）start）｛returntrue；｝if（visited〔start〕）｛returnfalse；｝visited〔start〕true；Trienodetrie；for（intistart；iword。size（）；i）｛charchword〔i〕；intindexcha；nodenodechildren〔index〕；if（nodenullptr）｛returnfalse；｝if（nodeisEnd）｛if（dfs（word，i1，visited））｛returntrue；｝｝｝returnfalse；｝voidinsert（conststringword）｛Trienodetrie；for（inti0；iword。size（）；i）｛charchword〔i〕；intindexcha；if（nodechildren〔index〕nullptr）｛nodechildren〔index〕newTrie（）；｝nodenodechildren〔index〕；｝nodeisEndtrue；｝｝；
　　JavaclassSolution｛TrietrienewTrie（）；publicListStringfindAllConcatenatedWordsInADict（String〔〕words）｛ListStringansnewArrayListString（）；Arrays。sort（words，（a，b）a。length（）b。length（））；for（inti0；iwords。length；i）｛Stringwordwords〔i〕；if（word。length（）0）｛continue；｝boolean〔〕visitednewboolean〔word。length（）〕；if（dfs（word，0，visited））｛ans。add（word）；｝else｛insert（word）；｝｝returnans；｝publicbooleandfs（Stringword，intstart，boolean〔〕visited）｛if（word。length（）start）｛returntrue；｝if（visited〔start〕）｛returnfalse；｝visited〔start〕true；Trienodetrie；for（intistart；iword。length（）；i）｛charchword。charAt（i）；intindexcha；nodenode。children〔index〕；if（nodenull）｛returnfalse；｝if（node。isEnd）｛if（dfs（word，i1，visited））｛returntrue；｝｝｝returnfalse；｝publicvoidinsert（Stringword）｛Trienodetrie；for（inti0；iword。length（）；i）｛charchword。charAt（i）；intindexcha；if（node。children〔index〕null）｛node。children〔index〕newTrie（）；｝nodenode。children〔index〕；｝node。isEndtrue；｝｝classTrie｛Trie〔〕children；booleanisEnd；publicTrie（）｛childrennewTrie〔26〕；isEndfalse；｝｝
　　Golangtypetriestruct｛children〔26〕trieisEndbool｝func（roottrie）insert（wordstring）｛node：rootfor，ch：rangeword｛chaifnode。children〔ch〕nil｛node。children〔ch〕trie｛｝｝nodenode。children〔ch〕｝node。isEndtrue｝func（roottrie）dfs（vis〔〕bool，wordstring）bool｛ifword｛returntrue｝ifvis〔len（word）1〕｛returnfalse｝vis〔len（word）1〕truenode：rootfori，ch：rangeword｛nodenode。children〔cha〕ifnodenil｛returnfalse｝ifnode。isEndroot。dfs（vis，word〔i1：〕）｛returntrue｝｝returnfalse｝funcfindAllConcatenatedWordsInADict（words〔〕string）（ans〔〕string）｛sort。Slice（words，func（i，jint）bool｛returnlen（words〔i〕）len（words〔j〕）｝）root：trie｛｝for，word：rangewords｛ifword｛continue｝vis：make（〔〕bool，len（word））ifroot。dfs（vis，word）｛ansappend（ans，word）｝else｛root。insert（word）｝｝return｝
　　CpublicclassSolution｛TrietrienewTrie（）；publicIListstringFindAllConcatenatedWordsInADict（string〔〕words）｛IListstringansnewListstring（）；Array。Sort（words，（a，b）a。Lengthb。Length）；for（inti0；iwords。Length；i）｛stringwordwords〔i〕；if（word。Length0）｛continue；｝bool〔〕visitednewbool〔word。Length〕；if（DFS（word，0，visited））｛ans。Add（word）；｝else｛Insert（word）；｝｝returnans；｝publicboolDFS（stringword，intstart，bool〔〕visited）｛if（word。Lengthstart）｛returntrue；｝if（visited〔start〕）｛returnfalse；｝visited〔start〕true；Trienodetrie；for（intistart；iword。Length；i）｛charchword〔i〕；intindexcha；nodenode。children〔index〕；if（nodenull）｛returnfalse；｝if（node。isEnd）｛if（DFS（word，i1，visited））｛returntrue；｝｝｝returnfalse；｝publicvoidInsert（stringword）｛Trienodetrie；for（inti0；iword。Length；i）｛charchword〔i〕；intindexcha；if（node。children〔index〕null）｛node。children〔index〕newTrie（）；｝nodenode。children〔index〕；｝node。isEndtrue；｝｝classTrie｛publicTrie〔〕children；publicboolisEnd；publicTrie（）｛childrennewTrie〔26〕；isEndfalse；｝｝
　　CtypedefstructTrie｛structTriechildren〔26〕；boolisEnd；｝Trie；defineTRIEINITIAL（node）do｛for（inti0；i26；i）｛（node）children〔i〕NULL；｝（node）isEndfalse；｝while（0）；staticvoidfreeTrie（Trienode）｛if（NULLnode）｛return；｝for（inti0；i26；i）｛if（nodechildren〔i〕！NULL）｛freeTrie（nodechildren〔i〕）；｝｝free（node）；｝staticintcmp（constvoidpa，constvoidpb）｛intlastrlen（（char）pa）；intlbstrlen（（char）pb）；returnlalb；｝booldfs（Trietrie，constcharword，intwordSize，intstart，intvisited）｛if（wordSizestart）｛returntrue；｝if（visited〔start〕）｛returnfalse；｝visited〔start〕1；Trienodetrie；for（intistart；iwordSize；i）｛charchword〔i〕；intindexcha；nodenodechildren〔index〕；if（nodeNULL）｛returnfalse；｝if（nodeisEnd）｛if（dfs（trie，word，wordSize，i1，visited））｛returntrue；｝｝｝returnfalse；｝voidinsert（Trietrie，constcharword，intwordSize）｛Trienodetrie；for（inti0；iwordSize；i）｛charchword〔i〕；intindexcha；if（nodechildren〔index〕NULL）｛nodechildren〔index〕（Trie）malloc（sizeof（Trie））；TRIEINITIAL（nodechildren〔index〕）；｝nodenodechildren〔index〕；｝nodeisEndtrue；｝charfindAllConcatenatedWordsInADict（charwords，intwordsSize，intreturnSize）｛intpos0；charans（char）malloc（sizeof（char）wordsSize）；Trietrie（Trie）malloc（sizeof（Trie））；TRIEINITIAL（trie）；qsort（words，wordsSize，sizeof（char），cmp）；for（inti0；iwordsSize；i）｛intlenstrlen（words〔i〕）；if（len0）｛continue；｝intvisited（int）malloc（sizeof（int）len）；memset（visited，0，sizeof（int）len）；if（dfs（trie，words〔i〕，len，0，visited））｛ans〔pos〕（char）malloc（sizeof（char）（len1））；strncpy（ans〔pos〕，words〔i〕，len）；ans〔pos〕〔len〕；pos；｝else｛insert（trie，words〔i〕，len）；｝free（visited）；｝freeTrie（trie）；returnSizepos；returnans；｝
　　复杂度分析时间复杂度：
　　其中n是数组words的长度，li是单词words〔i〕的长度。对数组words按照字符串的长度递增的顺序排序需要O（nlogn）的时间，判断单词words〔i〕是不是连接词的时间复杂度是O（li）。空间复杂度：
　　其中n是数组words的长度，li是单词words〔i〕的长度，S是字符集，这道题中S为全部小写英语字母，S26。空间复杂度主要取决于字典树，最坏情况下需要将所有的单词加入字典树。
　　BY
　　本文作者：力扣
　　声明：本文归力扣版权所有，如需转载请联系。