Concatenated Words | Python3 Solution | with comments | Time complexity analysis
\'\'\'\n\n\tdef findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        # creating a hashset of words for faster look-up\n        wordset
\'\'\'\n\n\tdef findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        # creating a hashset of words for faster look-up\n        wordset = set(words)\n        # List to store the final desired output\n        result = []\n        # Hashmap for keeping account of word of the wordset\n        dict_map = {}\n        \n        # DfS algorithm for calculating concatenated words\n        def dfs(word):\n            # if the word is already present in the hashMap, return its value\n            if word in dict_map:\n                return dict_map[word]\n            \n            # Going over the prefix and suffix of the given word to check whether they exist in the wordset\n            # If yes, then return True and update the hashMap value of that word to True\n            for indx in range(1,len(word)):\n                prefix = word[:indx]\n                suffix = word[indx:]\n                \n                if prefix in wordset and suffix in wordset:\n                    dict_map[word] = True\n                    return True\n                elif prefix in wordset and dfs(suffix):\n                    dict_map[word] = True\n                    return True\n            \n            dict_map[word] = False\n            return False\n        # Going over each word in words list\n        for word in words:\n            if dfs(word):\n                # Appending the word to the result \n                result.append(word)\n        return result\n    \nTime Complexity:- O(MN)\nHere,\nM --> Number of words in a word list\nN --> Length of word\n\nHope this helps. Thanks!
['Depth-First Search', 'Recursion', 'Ordered Set']