题目描述:
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/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。
cak1 发布于 2015年7月21日 17:44 #
拜读大神文章很多...请问是否能把the skyline problem也做一下?小弱现在还不知道怎么做...
在线疯狂 发布于 2015年7月22日 19:52 #
嘿嘿,其实那道题我也没做明白,会做了一定把解题报告给补上!
cak1 发布于 2015年7月22日 22:23 #
好啊多谢!!!