题目描述：

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

题目大意：

给定一个字符串s与一组单词的字典dict，在s中添加空格构造句子，使得句中的每一个单词都是字典中的单词。

返回所有可能的句子。

例如给定s = "catsanddog", dict = ["cat", "cats", "and", "sand", "dog"].

上例的一个可行解是：["cats and dog", "cat sand dog"]

解题思路：

记忆化搜索

在搜索过程中，使用字典tokenDict将已经搜索过的子句的拆解方案记录下来，从而实现DFS的剪枝。

Python代码：

class Solution:
    # @param s, a string
    # @param wordDict, a set<string>
    # @return a string[]
    def wordBreak(self, s, wordDict):
        tokenDict = dict()
        def dfs(s):
            ans = []
            if s in wordDict:
                ans.append(s)
            for x in range(len(s) - 1):
                prefix, suffix = s[:x + 1], s[x + 1:]
                if prefix not in wordDict:
                    continue
                rest = []
                if suffix in tokenDict:
                    rest = tokenDict[suffix]
                else:
                    rest = dfs(suffix)
                for n in rest:
                    ans.append(prefix + ' ' + n)
            tokenDict[s] = ans
            return ans
        return dfs(s)

 

本文链接：http://bookshadow.com/weblog/2015/07/21/leetcode-word-break-ii/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码