Word Break II

Question

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. You may assume the dictionary does not contain duplicate words.

Return all such possible sentences.

For example, given s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

A solution is ["cats and dog", "cat sand dog"].

Tags

• Backtracking
• Dynamic Programming

Thought

The solution is similar to the problem Word Break. Here, we need to use the dynamic programming table to track the divisible indices during the loop and skip the unnecessary forks during the backtracking. Otherwise, the code will cause TLE.

Code

class Solution(object):
    def dpSolver(self, s, wordDict):
        dp = [False for _ in xrange(len(s) + 1)]
        dp[0] = True
        for i in xrange(1, len(s) + 1):
            for j in xrange(i):
                if dp[j] and s[j:i] in wordDict:
                    dp[i] = True
                    break
        return dp

    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: List[str]
        """

        def dfs(validSentence, index):
            if index == len(s):
                res.append(" ".join(validSentence))
            for i in xrange(index + 1, len(s) + 1):
                if dp[i] is False:
                    continue
                if s[index: i] in wordDict:
                    dfs(validSentence + [s[index: i]], i)

        dp = self.dpSolver(s, wordDict)
        if dp[-1] is False:
            return []
        res = []
        dfs([], 0)
        return res