题目描述
给一字串s和单词的字典dict,在字串中增加空格来构建一个句子，并且所有单词都来自字典。
返回所有有可能的句子。
测试样例
输入："lintcode"，["de","ding","co","code","lint"]
输出：["lint code", "lint co de"]
解释：
插入一个空格是"lint code"，插入两个空格是 "lint co de"
输入："a"，[]
输出：[]
解释：字典为空
解题思路
1、DFS
自然而然容易想到用深搜来解决，而且代码也很精炼，整个dfs不到10行就可以搞定。
具体做法是每次深搜都取一定长度的前缀字符串，若其在词典中，则对后面的子串进行进一步的深搜；深搜的终止条件是当前字符串为空，则将目前为止获得的分词组合加入到最终结果。
整体思路是这样没错，但是如果仅仅是这样的话你会发现它会超时过不了，超时的是以下测试样例：
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"]
观察了下，发现字符串中的字母'b'在词典中每个词中都没有出现，于是在进行dfs前先对字符串和词典中所有的字母进行判断，若字符串中的所有字母不是词典中所有字母的子集，那么说明这是不可能分词成功的，直接返回空列表即可。加上这个条件，这种naive dfs的方案就能过了。
2、记忆化搜索I
其实整体思路和过程都和dfs差不多，只不过额外使用了一个dict来记录当前字符串与其子串所组合的分词结果，这样遇到重复的字符串时，就可以直接返回记录的结果而无需重复操作。需要注意的一点时，每次搜索时若当前字符串在词典中，则直接将其加入到分词组合的list中。
3、记忆化搜索II
记忆化搜索的另一种形式，上述的1、2都是从输入字符串的每个位置下手取前缀，而该方式是从词典中的每个词出发，若其是当前字符串的前缀，则将其和后缀子串返回的结果进行组合。同样地，如果该词与当前字符串完全一致，则直接将其加入分词组合的list中。
代码
1、DFS
class Solution:
"""
@param: s: A string
@param: wordDict: A set of words.
@return: All possible sentences.
"""
def wordBreak(self, s, wordDict):
if not wordDict:
return []
s1 = set(s)
s2 = set(''.join(wordDict))
if not s1.issubset(s2):
return []
result = []
self.dfs(s, wordDict, [], result)
return result
def dfs(self, s, wordDict, tmp, result):
if not s:
result.append(' '.join(tmp))
return
for i in range(1, len(s) + 1):
if s[:i] in wordDict:
self.dfs(s[i:], wordDict, tmp + [s[:i]], result)
2、 记忆化搜索I
class Solution:
"""
@param: s: A string
@param: wordDict: A set of words.
@return: All possible sentences.
"""
def wordBreak(self, s, wordDict):
if not wordDict:
return []
return self.dfs(s, wordDict, {})
def dfs(self, s, wordDict, memo):
"""记忆化搜索"""
if s in memo:
return memo[s]
if not s:
return []
partitions = []
for i in range(1, len(s)):
if s[:i] in wordDict:
for sub_partition in self.dfs(s[i:], wordDict, memo):
# 当前前缀与后面子字符串的各个分割结果组合
partitions.append('{} {}'.format(s[:i], sub_partition))
# 若当前整个字符串在词典中，要加入结果中
if s in wordDict:
partitions.append(s)
# 存储记忆
memo[s] = partitions
return partitions
3、记忆化搜索II
classSolution:
"""
@param: s: A string
@param: wordDict: A set of words.
@return: All possible sentences.
"""
defwordBreak(self, s, wordDict): if not wordDict:
return []
return self.dfs(s, wordDict, {})
defdfs(self, s, wordDict, memo):
"""记忆化搜索"""
if s in memo:
return memo[s]
if not s:
return []
partitions = []
for word in wordDict:
# 词典中的词必须是当前字符串的前缀 # 另外，注意需要判断word是""的情况！
if not (s.startswith(word) and word):
continue
if word == s:
partitions.append(word)
else:
for sub_partition in self.dfs(s[len(word):], wordDict, memo):
partitions.append('{} {}'.format(word, sub_partition))
# 存储记忆 memo[s] = partitions
return partitions
网友评论