For this question, first I thought of some basic method.
basic dfs
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
ans = []
self.helper([],s,wordDict,ans)
return ans
def helper(self,path,s,wordDict,ans):
if not s:
ans.append(" ".join(path))
for i in xrange(0,len(s)):
if s[0:i + 1] in wordDict:
self.helper(path + [s[0:i + 1]],s[i + 1:],wordDict,ans)
use dp to memorize from forward to backward
this solution use dynamic programming to memorize each [0,i] from first to last.
so this is suitable each list for [0,i] is very short.
i.e dict is very short.
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
dp = [[] for i in xrange(len(s) + 1)]
dp[0] = [""]
for i in xrange(1, len(s) + 1):
for j in xrange(0,i):
sub = s[j : i]
if sub in wordDict:
for l in dp[j]:
new_sub = l + " " + sub
dp[i].append(new_sub)
res = map(lambda x : x[1:],dp[len(s)])
return res
** Anyway, both the methods cannot pass the test.
The first one, basic dfs solution got TLE, since some suffix got calculated for so many times.
The second one, got MLE, since we memorize so many result that will not have effect on the final result.**
final optimization -- dfs + memo
Do the dfs and memo the suffix.
Then the memo size will not more than final results.
class Solution(object):
def wordBreak(self, s, wordDict):
"""
:type s: str
:type wordDict: Set[str]
:rtype: List[str]
"""
if not s:
return None
memo = {}
self.helper(s,wordDict,memo)
return memo[s]
def helper(self,s,wordDict,memo):
if not s:
return [""]
if s in memo:
return memo[s]
ans = []
for i in xrange(0,len(s)):
sub = s[0:i + 1]
if sub in wordDict:
next = self.helper(s[i + 1:],wordDict,memo)
for each in next:
if not each:
ans.append(sub)
else:
ans.append(sub + " " + each)
memo[s] = ans
return ans
