Word Break II

题目描述

解题方法

DP的方法

还是可以用DP

DFS

这一题与1一样，也可以用DP的方法来做，但是在要求所有解的问题中，DP与DFS的效果其实差不多。 如果用DP的话，就要记录下i可以由之前的哪一个index break而来，最后重建的时候code也比较复杂。 我们可以用DFS + backtracking的方法，并且减去一些不必要的计算。 注意点

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

Solution

DP的方法

class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: Set[str]
        :rtype: List[str]
        """
        if not s:
            return True
        length = len(s)
        dp = [False for i in range(length+1)]
        path = [None for i in range(length+1)]
        dp[0] = True
        result = []

        for i in range(1, length+1): # i表示i-1 index
            for j in range(i):
                if s[j:i] in wordDict and dp[j]:
                    dp[i] = True
                    if path[i]:
                        path[i].append((j, s[j:i]))
                    else:
                        path[i] = [(j, s[j:i])]
        if path[length]:
            self.dfs(result, path, [], length)
            for i in range(len(result)):
                result[i].reverse()
                result[i] = " ".join(result[i])
        return result

    def dfs(self, result, path, cur_list, index):
        if index == 0:
            result.append(list(cur_list))
            return
        for p in path[index]:
            next_index = p[0]
            word = p[1]
            cur_list.append(word)
            self.dfs(result, path, cur_list, next_index)
            cur_list.pop()

DFS

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

    def helper(self, result, s, wordDict, index, cur_list):
        if self.check(s[index:], wordDict):
            if index >= len(s):
                new_list = " ".join(cur_list)
                result.append(new_list)
                return
            for i in range(index+1, len(s)+1):
                if s[index:i] in wordDict:
                    cur_list.append(s[index:i])
                    self.helper(result, s, wordDict, i, cur_list)
                    cur_list.pop()

    def check(self, s, wordDict):
        dp = [False for i in range(len(s)+1)]
        dp[0] = True

        for i in range(1, len(s)+1):
            for j in range(i):
                if s[j:i] in wordDict and dp[j]:
                    dp[i] = True

        return dp[len(s)]

Reference