本文共 1704 字，大约阅读时间需要 5 分钟。

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

题意

与word-break相比，这里需要列举具体的结果，而不是结果有多少种，或者要得出True or False 的结果，必用dfs.

思路

第一种思路是暴力dfs, 简单明了，一看就会；第一种结合了word-break的dp,就是在dfs前先检查s到底能不能分，比较精巧，大大节约了时间。

暴力dfs python实现

class Solution(object):    def __init__(self, wordDict):        self.res = []        self.wordDict = wordDict    def dfs(self, s, stringlist=''):        if not s:            self.res.append(stringlist[1:])        # for 循环确保取到s的最后一个        for i in range(1, len(s)+1):            if s[:i] in self.wordDict:                self.dfs(s[i:], stringlist+' '+s[:i])        return self.resif __name__ == '__main__':    s = 'catsanddog'    dict = ['cat', 'cats', 'and', 'sand', 'dog']    so = Solution(dict)    print(so.dfs(s))

dp+dfs python实现

class Solution(object):    def __init__(self, wordDict):        self.res = []        self.wordDict = wordDict    def dfs(self, s, stringlist=''):        if self.dp(s):            if not s:                self.res.append(stringlist[1:])            # for 循环确保取到s的最后一个            for i in range(1, len(s)+1):                if s[:i] in self.wordDict:                    self.dfs(s[i:], stringlist+' '+s[:i])            return self.res    def dp(self, s):        n = len(s)        dp = [False] * (n+1)        dp[0] = True        for i in range(n):            for j in range(i+1):                if dp[j] and s[j:i+1] in self.wordDict:                    dp[i+1] = True        return dp[n]

转载地址：http://aejmb.baihongyu.com/