嗯绞愚，超時(shí)了
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
res = []
self.dfs(s, 0, "", res, wordDict)
return res
def dfs(self, s, start, temp, res, wordDict):
if start == len(s):
res.append(temp)
return
for i in range(start, len(s)):
t = s[start:i+1]
if t in wordDict:
end = i+1
if end != len(s):
self.dfs(s, end, temp+t+' ', res, wordDict )
else:
self.dfs(s, end, temp+t, res, wordDict)
剪枝了的做法
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: List[str]
:rtype: List[str]
"""
res = []
f = []
self.dfs(s, 0, [], res, wordDict,f)
return res
def dfs(self, s, start, temp, res, wordDict,f):
if start == len(s):
res.append(' '.join(temp[:]))
return True
if start in f:
return False
found = False
for i in range(start+1, len(s)+1):
if i in f:
continue
t = s[start:i]
if t in wordDict:
print t
temp.append(t)
if self.dfs(s, i, temp, res, wordDict, f):
found = True
temp.pop()
if not found:
f.append(start)
return found
