[140]Word Break II

leetcode

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