Word Break II

题目描述

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

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"].

解题方法

这一题与1一样，也可以用DP的方法来做，但是在要求所有解的问题中，DP与DFS的效果其实差不多。

如果用DP的话，就要记录下i可以由之前的哪一个index break而来，最后重建的时候code也比较复杂。

我们可以用DFS + backtracking的方法，并且减去一些不必要的计算。

注意点

  • 在DFS中加入先判断是否能够word break的逻辑，这样可以避免不必要的计算

Solution

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        results = []
        if not s or not wordDict:
            return []

        self.helper(results, s, 0, wordDict, [])
        return results


    def helper(self, results, s, start, wordDict, curList):
        if self.check(s[start:], wordDict):
            if start >= len(s):
                newList = " ".join(curList)
                results.append(newList)
                return

            for i in range(start+1, len(s)+1):
                if s[start:i] in wordDict:
                    curList.append(s[start:i])
                    self.helper(results, s, i, wordDict, curList)
                    curList.pop()

    def check(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: bool
        """
        if not wordDict:
            return False

        length = len(s)

        canBreak = [False for i in range(length+1)]
        canBreak[0] = True

        for i in range(1, length+1):
            for j in range(i):
                if canBreak[i]:
                    continue
                if (s[j:i] in wordDict) and canBreak[j]:
                    canBreak[i] = True

        return canBreak[length]

Reference