Python Template - Word Break I, Word Break II, Concatenated Words
Code & Idea for questions :\n1. Word Break : Ques No. 139\n2. Word Break II : Ques No. 140\n3. Concatenated Words : Ques No. 472\n\nBasic idea is same for all, 
Code & Idea for questions :\n1. [Word Break : Ques No. 139](http://leetcode.com/problems/word-break/)\n2. [Word Break II : Ques No. 140](http://leetcode.com/problems/word-break-ii/)\n3. [Concatenated Words : Ques No. 472](http://leetcode.com/problems/concatenated-words/)\n\nBasic idea is same for all, find if string can be broken down to smaller string. Word Break I template follows other two.\n\n### Word Break I\nUsing dynamic programming to calculate if word break is possible or not\n\n```\nclass Solution(object):\n    def wordBreak(self, s, wordDict):\n        """\n        :type s: str\n        :type wordDict: List[str]\n        :rtype: bool\n        """\n        dp = [False] * (len(s) + 1)\n        dp[0] = True\n        wordDict = set(wordDict)\n        \n        for i in range(len(s)+1):\n            for j in range(i):\n                if dp[j] and s[j:i] in wordDict:\n                    dp[i] = True\n        return dp[-1]\n```\n\n### Word Break II\nThis is backtracking plus dynamic programming. We use dp array generated from word break I to figure out remaining string can be splitted or not, this reduces lot of backtracking calls. \n```\nclass Solution(object):\n    def wordBreak(self, s, wordDict):\n        """\n        :type s: str\n        :type wordDict: List[str]\n        :rtype: List[str]\n        """\n        if not s:\n            return [""]\n        \n        self.res = []\n        self.wordDict = set(wordDict)\n        self.dp = self.isWordBreak(s, wordDict)\n        self.backtrack(s, 0, [])\n        \n        return self.res\n    \n    def backtrack(self, s, idx, path):\n        # Before we backtrack, we check whether the remaining string \n        # can be splitted by using the dictionary,\n        # in this way we can decrease unnecessary computation greatly.\n        if self.dp[idx+len(s)]: # if word break possible then only proceed\n            if not s:\n                self.res.append(\' \'.join(path))\n            else:\n                for i in range(1, len(s)+1):\n                    if s[:i] in self.wordDict:\n                        self.backtrack(s[i:], idx+i, path + [s[:i]])\n        \n    # this is from Word Break I\n    def isWordBreak(self, s, wordDict):\n        dp = [False] * (len(s) + 1)\n        dp[0] = True\n        \n        for i in range(len(s)+1):\n            for j in range(i):\n                if dp[j] and s[j:i] in wordDict:\n                    dp[i] = True\n        return dp\n```\n\n### Concatenated Words\nConcatenated Words is the reverse of Word Break I, so can be broken down to Word Break I. \n1. Sort the words according to shortest length since short ones form long words\n2. for each word start building our dictionary of words and check if word split is possible or not\n\n```\nclass Solution(object):\n    def findAllConcatenatedWordsInADict(self, words):\n        """\n        :type words: List[str]\n        :rtype: List[str]\n        """\n        res = []\n        preWords = set()\n        \n        # asc order of word length, since longer words are formed by shorter words\n        words.sort(key = len)\n        \n        # for each short word start building preWords\n        for word in words:\n            if self.wordBreak(word, preWords):\n                res.append(word)\n            preWords.add(word)\n        \n        return res\n    \n    # Word Break I template\n    def wordBreak(self, string, words):\n        if not words:\n            return False\n        \n        dp = [False] * (len(string) + 1)\n        dp[0] = True\n        \n        for i in range(len(string)+1):\n            for j in range(i):\n                if dp[j] and string[j:i] in words:\n                    dp[i] = True\n                    break\n        \n        return dp[-1]\n```
['Dynamic Programming', 'Depth-First Search', 'Python']