Word Break II

Problem: Word Break II

The general idea is to run backtracking on the string to do word break. However it's very time-consuming. A trick is that we can store results for certain sub-strings so that after one depth-first search, the results can be used on another depth-first search to save time.

Code in Python:

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        max_len = 0
        for word in wordDict:
            max_len = max(max_len, len(word))
        solutions = {}
        def helper(start):
            if start in solutions: return solutions[start]
            solutions[start] = []
            string = ""
            for i in xrange(start, min(start+max_len, len(s))):
                string += s[i]
                if string in wordDict:
                    if i == len(s)-1:
                        solutions[start].append(string)
                    else:
                        for solution in helper(i+1):
                            solutions[start].append(string + " " + solution)
            return solutions[start]
        return helper(0)