My 82ms Python DP Solution

  • 1

    Use Word Break I's code to check if a case is worth doing to avoid TLE. The rest is similar to Word Break I except now it stores all possible substrings in the dp[i] cell instead.

    class Solution(object):
        def wordBreak_check(self, s, wordDict):
            n = len(s)
            dp = [False for i in range(n+1)] 
            dp[0] = True
            for i in range(1,n+1):
                for w in wordDict:
                    if dp[i-len(w)] and s[i-len(w):i]==w: 
            return dp[-1]
        def wordBreak(self, s, wordDict):
            if not self.wordBreak_check(s, wordDict):
                return []
            n = len(s)
            dp = [[]for i in range(n+1)] 
            for i in range(1,n+1):
                tmp = []
                for j in range(0, i):
                    cur_sub = s[j:i]
                    if (len(dp[j])> 0 and cur_sub in wordDict):
                        [tmp.append(x+""+cur_sub) if x== "" else tmp.append(x+" "+cur_sub) for x in dp[j]]
                dp[i] = tmp
            return dp[-1]

Log in to reply

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