✔️ [Python3] TRIE WITH RECURSION ᕕ( ᐛ )ᕗ, Explained
UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.\n\nWe create a trie data structure from all given words. Then w
**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**\n\nWe create a trie data structure from all given words. Then we iterate over the characters of every word. When we see that a current prefix is in the trie, we call a recursive function asking whether the slice of the word starting after the prefix is a concatenated word.\n\nTime: **O(n)**\nSpace: **O(n)**\n\n```\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        ddic = lambda: defaultdict(ddic)\n        trie = ddic()\n        \n        for word in words:\n            cur = trie\n            for char in word:\n                cur = cur[char]\n\n            cur[\'end\'] = True\n        \n        def isConcat(word, start):\n            cur = trie\n            for i in range(start, len(word)):\n                char = word[i]\n                if char not in cur:\n                    return False\n                cur = cur[char]\n\n                if \'end\' in cur:\n                    if i + 1 == len(word):\n                        # tricky part that helps us distinguish simple word from concat word\n                        return start != 0\n                    \n                    if isConcat(word, i + 1):\n                        return True\n\n            return False\n            \n        return [word for word in words if isConcat(word, 0)]\n```\n\n**UPVOTE if you like (\uD83C\uDF38\u25E0\u203F\u25E0), If you have any question, feel free to ask.**
['Python3']