Simple and concise python bottom-up DP


  • 0
    N

    The code is self-explanatory.
    Note that the Set membership test (s[j:i] in wordDict) in python is O(1).

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: bool
            """
            dp = [False]*(len(s)+1)
            dp[0] = True
            for i in range(1, len(s)+1):
                for j in range(0, i):
                    if dp[j] and s[j:i] in wordDict:
                        dp[i] = True
                        break
            return dp[len(s)]
    

Log in to reply
 

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