[PYTHON] , VERY EASY,DP, RECURSION, MEMOISATION, Space and time optimised
First Lets look at the recursion solution so that we get the clarity and then we can move to dp solution\n\nclass Solution:\n    def findAllConcatenatedWordsInA
First Lets look at the recursion solution so that we get the clarity and then we can move to dp solution\n```\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        # helper function to check if a given word can be formed by concatenating \n        # two or more words in the input list\n        def can(w,dit):\n            for i in range(1,len(w)):\n                # check the left part of the word\n                lf=w[:i]\n                # check the right part of the word\n                rt=w[i:]\n                if lf in dit:\n                    # if left part of the word is in the input set, check if the right part is in the set\n                    # or can be formed by concatenating other words in the set\n                    if rt in dit or can(rt,dit):\n                        return True\n            return False\n        # initialize an empty list to store concatenated words\n        res=[]\n        # create a set of all words from the input list to improve lookup time\n        dit = set(list(words))\n        for w in words:\n            # check if the word can be formed by concatenating other words in the set\n            if can(w,dit):\n                # if it can, add it to the list of concatenated words\n                res.append(w)\n                \n        return res\n```\n\nNow lets look a bit space optimized solution\n**Space optimized**\n```\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        def can(w,dit):\n            for i in range(mini,len(w)):\n                lf=w[:i]\n                rt=w[i:]\n                if lf in dit:\n                    if rt in dit or can(rt,dit):\n                        return True\n            return False\n        res=[]\n        dit = set(list(words))\n        mini=10000\n        for w in words:\n            mini=min(len(w),mini)\n        for w in words:\n            if can(w,dit):\n                res.append(w)\n                \n        return res\n```\nNow lets look at the most optimized\n**DP solution most optimize**\n```\nclass Solution:\ndef findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n\tdef can(w,dit):\n\t\tif w in dp:\n\t\t\treturn True\n\t\tfor i in range(mini,len(w)):\n\t\t\tlf=w[:i]\n\t\t\trt=w[i:]\n\t\t\tif lf in dit:\n\t\t\t\tif rt in dit or can(rt,dit):\n\t\t\t\t\tdp.append(w)\n\t\t\t\t\treturn True\n\t\treturn False\n\tres=[]\n\tdit = set(list(words))\n\tmini=10000\n\tdp=[]\n\tfor w in words:\n\t\tmini=min(len(w),mini)\n\tfor w in words:\n\t\tif can(w,dit):\n\t\t\tres.append(w)\n\n\treturn res\n```\nHope it helps \n**UPVOTE** if helped\nfeel free to post query \n\t
['Dynamic Programming', 'Recursion', 'Python']