Python DP


  • 0
    class Solution(object):
        def checkWordBreak(self, s, wordDict):
            d = set(wordDict)
            lens = map(len, wordDict)
            dp = [False] * (len(s) + 1)
            dp[0] = True
            for i in range(len(s)):
                for length in lens:
                    dp[i+1] = dp[i + 1] or dp[i - length + 1] and s[i - length + 1:i+1] in d
                    if dp[i + 1]:
                        break
            return dp[-1]
        
        def wordBreak(self, s, wordDict):
            if not self.checkWordBreak(s, wordDict):
                return []
            dp = [[] for _ in range(len(s) + 1)]
            dp[0].append("")
            d = set(wordDict)
            lens = list(set(map(len, wordDict)))
            for i in range(len(s)):
                for length in lens:
                    if i - length + 1 >= 0 and s[i - length + 1: i + 1] in d and len(dp[i - length + 1]) > 0:
                        if i - length + 1 == 0:
                            dp[i + 1].append(s[i - length + 1: i + 1])
                        else:
                            dp[i + 1].extend([prev + " " + s[i - length + 1: i + 1] for prev in dp[i - length + 1]])
            return dp[-1]
    

Log in to reply
 

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