Python | Beats 97% runtime | Trie
\nclass Solution:\ndef findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n\ttrie={}\n\tfor w in words:\n\t\troot=trie\n\t\tfor s in w:\n\t\t
```\nclass Solution:\ndef findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n\ttrie={}\n\tfor w in words:\n\t\troot=trie\n\t\tfor s in w:\n\t\t\tif s not in root:\n\t\t\t\troot[s]={}\n\t\t\troot=root[s]\n\t\troot["$"]=True\n\n\t@lru_cache(None)\n\tdef find(w):\n\t\tif not w:\n\t\t\treturn True\n\t\ttmp=trie\n\t\tval=False\n\t\tfor i,s in enumerate(w):\n\t\t\tif s not in tmp:\n\t\t\t\tbreak\n\t\t\ttmp=tmp[s]\n\t\t\tif "$" in tmp:\n\t\t\t\tval|= find(w[i+1:])\n\t\t\t\tif val:\n\t\t\t\t\tbreak\n\t\treturn val\n\n\tres=[]\n\tfor w in words:\n\t\troot=trie\n\t\tfor i,s in enumerate(w):\n\t\t\troot=root[s]\n\t\t\tif "$" in root:\n\t\t\t\tif i!=len(w)-1 and find(w[i+1:]):\n\t\t\t\t\tres.append(w)\n\t\t\t\t\tbreak\n\treturn res\n\n```\n
['Trie', 'Python']