Python DP solution

  • 0
        def wordBreak(self, s, wordDict):
            n = len(s)
            r = [[False for _ in xrange(n+1)] for _ in xrange(n)]
            for i in xrange(0, n):
                for j in xrange(i+1, n+1):
                    if i == 0:
                        r[i][j] = s[:j] in wordDict
                    elif s[i:j] in wordDict:  
                        r[i][j] = r[i-1][i] or r[i-1][j]
                        r[i][j] = r[i-1][j]
            return r[n-1][n]

Log in to reply

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