Python solutions: top-down DP, Trie + DFS
Please see and vote for my Python DP solutions for\n139. Word Break\n140. Word Break II\n472. Concatenated Words\n\nMethod 1: top-down DP (444 ms, beat 52%)\nLe
Please see and vote for my Python DP solutions for\n[139. Word Break](https://leetcode.com/problems/word-break/discuss/322388/Standard-DP-solutions-(Bottom-up-Top-down))\n[140. Word Break II](https://leetcode.com/problems/word-break-ii/discuss/322400/Standard-Python-DP-solutions-(Bottom-up-Top-down))\n[472. Concatenated Words](https://leetcode.com/problems/concatenated-words/discuss/322444/Python-solutions%3A-top-down-DP-Trie)\n\nMethod 1: top-down DP (444 ms, beat 52%)\nLet dp[i] = whether s[i:len(s)] can be segmented into a space-separated sequence of words, i=0,1,2,..., len(s).\nThe possible values of dp[i] are: \n0 means s[i:len(s)] cannot be sucessfully segmented, \n1 means s[i:len(s)] is in words and cannot be sucessfully segmented,\n2 means s[i:len(s)] can be segmented into a space-spearated sequence of at least two words.\n```\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        def recursive(s, i, n):\n            if i in dp:\n                return dp[i]\n            j = i + 1\n            while j <= n:\n                if s[i:j] in word_set and recursive(s, j, n):\n                    dp[i] = 2 if j < n else 1\n                    return dp[i]\n                j += 1\n            dp[i] = 0\n            return dp[i]\n            \n        word_set = set(words)\n        res = []\n        for w in words:\n            n = len(w)\n            dp = {n: 1}\n            if recursive(w, 0, n) > 1:\n                res.append(w)\n        return res\n```\n\nMethod 2: implement same algorithm via Trie + DFS (1616 ms, beat 6.95%)\n\nPlease see and vote for my solutions for\n[208. Implement Trie (Prefix Tree)](https://leetcode.com/problems/implement-trie-prefix-tree/discuss/320224/Simple-Python-solution)\n[1233. Remove Sub-Folders from the Filesystem](https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/discuss/409075/standard-python-prefix-tree-solution)\n[1032. Stream of Characters](https://leetcode.com/problems/stream-of-characters/discuss/320837/Standard-Python-Trie-Solution)\n[211. Add and Search Word - Data structure design](https://leetcode.com/problems/add-and-search-word-data-structure-design/discuss/319361/Simple-Python-solution)\n[676. Implement Magic Dictionary](https://leetcode.com/problems/implement-magic-dictionary/discuss/320197/Simple-Python-solution)\n[677. Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/discuss/320237/Simple-Python-solution)\n[745. Prefix and Suffix Search](https://leetcode.com/problems/prefix-and-suffix-search/discuss/320712/Different-Python-solutions-with-thinking-process)\n[425. Word Squares](https://leetcode.com/problems/word-squares/discuss/320916/Easily-implemented-Python-solution%3A-Backtrack-%2B-Trie)\n[472. Concatenated Words](https://leetcode.com/problems/concatenated-words/discuss/322444/Python-solutions%3A-top-down-DP-Trie)\n[212. Word Search II](https://leetcode.com/problems/word-search-ii/discuss/319071/Standard-Python-solution-with-Trie-%2B-Backtrack)\n[336. Palindrome Pairs](https://leetcode.com/problems/palindrome-pairs/discuss/316960/Different-Python-solutions%3A-brute-force-dictionary-Trie)\n\n```\nclass TrieNode():\n    def __init__(self):\n        self.children = {}\n        self.isEnd = False\n\nclass Trie():\n    def __init__(self, words):\n        self.root = TrieNode()\n        for w in words:\n            if w:\n                self.insert(w)\n    \n    def insert(self, word):\n        node = self.root\n        for char in word:\n            if char not in node.children:\n                node.children[char] = TrieNode()\n            node = node.children[char]\n        node.isEnd = True\n\nclass Solution:\n    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:\n        def dfs(node, i, w, space_inserted):\n            if i == len(w):\n                return node.isEnd and space_inserted\n            if node.isEnd:\n                if dfs(trie.root, i, w, True):\n                    return True\n            if w[i] not in node.children:\n                return False\n            else:\n                return dfs(node.children[w[i]], i + 1, w, space_inserted)\n        \n        trie = Trie(words)\n        res = []\n        for w in words:\n            if dfs(trie.root, 0, w, False):\n                res.append(w)\n        return res\n```
[]