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]，最终只能访问到i1，最大就是length1.
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
[Python] 46ms bottomup DP and DFS.


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 ifs[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]，最终只能访问到i1，最大就是length1. 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