Python Trie solution explained
This question is very similar to 208. Implement Trie (Prefix Tree) with one modification. Apart from searching for a word in the trie, we should also keep track
This question is very similar to [208. Implement Trie (Prefix Tree)](http://leetcode.com/problems/implement-trie-prefix-tree/) with one modification. Apart from searching for a word in the trie, we should also keep track of smaller words encountered during the search. \n\n1. We insert all the words into the `trie`. \n2. Iterate through each word and check if we can successfully perform `DFS`.\n\t2.1 If yes, add the word to `result`\n3. Return the `result`\n\nDuring the `DFS`, we keep track of 4 parameters: \n`word`  - word to be searched\n`start` - to track the current character of the `word` \n`root`   -  root of the `trie`\n`count` - number of smaller words encountered so far\n\nWe iterate through the characters of the `word` one by one starting from `start`.  Check if the current character is a word ending and also if it is the last character of the `word`. We make a decision based on the `count` value. Otherwise, we recur for remaining indices of the `word` with `count ` increased by 1. \n\nHead over to [link](http://skdoosh-leetcode.herokuapp.com) for more python solutions to leetcode problems and star my [github repo](https://github.com/Anirudh-Muthukumar/Leetcode-Solutions) if you like my work. \n\n```\nimport collections\n\nclass TrieNode:\n    def __init__(self):\n        self.children = collections.defaultdict(TrieNode)\n        self.isEnd = False\n\nclass Trie:\n    def __init__(self):\n        self.root = TrieNode()\n    \n    def insert(self, word):\n        marker = self.root\n        for ch in word:\n            marker = marker.children[ch]\n        marker.isEnd = True\n\n\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words):\n        \n        def dfs(word, start, root, count):\n            n = len(word)\n            marker = root\n            for i in range(start, n):\n                marker = marker.children[word[i]]\n                if marker.isEnd:           # smaller word encountered\n                    if i == n-1:               # leaf node\n                        return count>=1\n                    elif dfs(word, i+1, root, count+1):     # increment the count and start a new DFS\n                        return True\n            return False\n        \n        res = []\n        trie = Trie()\n        for word in words:\n            trie.insert(word)\n\n        for word in words:\n            if dfs(word, 0, trie.root, 0):\n                res += word,\n        \n        return res\n```\n            \n        \n\n        \n        \n        \n\n\n
['Depth-First Search', 'Trie', 'Recursion', 'Python3']