# [Python] 46ms bottom-up DP and DFS.

• ``````class Solution(object):

def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
res = []
length = len(s)
# DP[j]：表示[j:length)能否切分，使得子串能够被包含在worddict中。
DP = [False] * (length + 1)
DP[length] = True
# bottom to up
for j in range(length, -1, -1):
for i in range(j - 1, -1, -1):
if DP[j] and (s[i: j] in wordDict):
DP[i] = True

def DFS(index, valueList):
# cut
if DP[index]:  # 从下标Index开始，划分子串，能够满足题目条件，就进行递归
if index == length:
res.append(valueList[1:])
return

#记得这边是length+1，i能够达到的最大的是length,在切片的时候[index:i]，最终只能访问到i-1，最大就是length-1.
for i in range(index + 1, length + 1):
if s[index:i] in wordDict and DP[i]:
DFS(i, valueList + " " + s[index : i])

DFS(0, "")
return res
``````

• Hi,

Thanks for sharing this amazing code.

Your DFS part was quite neat, and I got that part. Yet the first part to get DP why did you go through the string from right to left?
I have my own DP list, but mine was going from the left to right. `DP[j]` will be if `s[0:j]` can be cut.

Yours worked well, but my method had a TLE. I was very curious of the difference. Thanks!

• Sorry, I have seen your problem right now. I have wrote down the code follow your idea and AC. However, I find that the run time is not very good compare to `from bottom to up`.

``````class Solution(object):

def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
res = []
length = len(s)
# DP[j]：表示[0 : j)能否切分，使得子串能够被包含在worddict中。
DP = [False] * (length + 1)
DP[0] = True

for j in range(0, length + 1):
for i in range(j + 1, length + 1):
if DP[j] and (s[j : i] in wordDict):
DP[i] = True

def DFS(index, valueList):
# cut
if DP[index]:  # 从下标Index开始，划分子串，能够满足题目条件，就进行递归
if index == 0:
res.append(valueList[:-1])
return

#记得这边是length+1，i能够达到的最大的是length,在切片的时候[index:i]，最终只能访问到i-1，最大就是length-1.
for i in range(index - 1, -1, -1):
if s[i : index] in wordDict and DP[i]:
DFS(i, s[i : index] + " " + valueList)

DFS(length, "")
return res
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.