# Unexpectedly Beats 100% Python Solution (Dynamic Programming & Backtracking)

• ``````    def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
from copy import deepcopy

if not s or not wordDict:
return []

min_len, max_len = float('inf'), float('-inf')
for word in wordDict:
min_len = min(min_len, len(word))
max_len = max(max_len, len(word))

# dp.
n = len(s)
dp = [False] * n
start = [[] for i in xrange(n)]
for end_index in xrange(min_len - 1, n):
start_index = end_index - min_len + 1
while start_index >= 0 and end_index - start_index + 1 <= max_len:
word = s[start_index : end_index + 1]
if word in wordDict and (start_index == 0 or dp[start_index - 1]):
dp[end_index] = True
start[end_index].append(start_index)
start_index -= 1

# bt: construct result.
def helper(s, dp, start, end_index, res, ass):
if end_index >= 0:
for start_index in start[end_index]:
word = s[start_index : end_index + 1]
ass2 = deepcopy(ass)
if not ass2:
ass2.append([word])
else:
for a in ass2:
a.append(word)
if start_index == 0:
for a in ass2:
a.reverse()
res.append(' '.join(a))
else:
helper(s, dp, start, start_index - 1, res, ass2)
return None

res = []
helper(s, dp, start, n - 1, res, [])
return res
``````

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