# An elegant python solution with DP

• Basic idea is starting from left most character of string, increase the index, if s[:idx+1] is a valid word, try generate all combinations of s[idx+1:]. Continue doing this until index reaches the end of string. This is a recursive solution, so each time all word break options are calculated, cache them.

``````class Solution:
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def wordBreak(self, s, dict):
self.dict = dict
self.cache = {}
return self.break_helper(s)

def break_helper(self, s):
combs = []
if s in self.cache:
return self.cache[s]
if len(s) == 0:
return []

for i in range(len(s)):
if s[:i+1] in self.dict:
if i == len(s) - 1:
combs.append(s[:i+1])
else:
sub_combs = self.break_helper(s[i+1:])
for sub_comb in sub_combs:
combs.append(s[:i+1] + ' ' + sub_comb)

self.cache[s] = combs
return combs``````

• wa, we have very close answer:

``````class Solution:

def __init__(self):
self.saved = {}

def wordBreak(self, s, dict):
self.saved.clear()
size = len(s)
return self.wordBreakImpl(s, dict)

def wordBreakImpl(self, s, dict):
if s in self.saved:
return self.saved[s]
else:
ret = []
for i in range(0, len(s)):
subs = s[0:i+1]
if subs in dict:
if (i + 1) == len(s):
currResult = [s]
else:
sentences = self.wordBreakImpl(s[i+1:], dict)
currResult = map(lambda s: subs + " " + s, sentences)
ret += currResult

self.saved[s] = ret
return ret``````

• I guess your code will TLE when input is:
"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
["a", "aa", "aaa", "aaaa", "aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaaa","aaaaaaaaaaaa"]
the code

``````for sub_comb in sub_combs:
``````

sub_combs may be very large

• Why? Any solution needs to traverse all possible splits. If you think this one is too slow, could share your faster solution?

• This post is deleted!

• Same idea, but bottom-up DP.
With optimization in only checking all possible word length in the following line.

`````` for wordLen in wordLenList:
``````

AC in 46 ms. Full solution

``````class Solution:
# @param s, a string
# @param dict, a set of string
# @return a list of strings
def wordBreak(self, s, dict):
sentences = [[] for i in range(len(s))]
wordLenList = set(map(len, dict))
for startIndex in xrange(len(s) - 1, -1, -1):
for wordLen in wordLenList:
if startIndex + wordLen > len(s) or s[startIndex: startIndex + wordLen] not in dict:
continue
if startIndex + wordLen == len(s):
sentences[startIndex].append(s[startIndex: startIndex + wordLen])
else:
for sentence in sentences[startIndex + wordLen]:
sentences[startIndex].append(s[startIndex: startIndex + wordLen] + " " + sentence)
return sentences[0]``````

• It fails the new test case baaaaa....

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