Concise Python DP solution

  • 3
    class Solution(object):
        def wordBreak(self, s, wordDict):
            n = len(s)
            is_breakable = [False] * (n+1)
            is_breakable[0] = True
            for i in xrange(1,n+1):
                for j in xrange(0,i):
                    if is_breakable[j] and s[j:i] in wordDict:
                        is_breakable[i] = True
            return is_breakable[n]

Log in to reply

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