Simple DP solution in python O(N^2)


  • 0
    A

    DP[i] mean if the string end in index, if it can be space-sparated.

    class Solution:
    # @param s, a string
    # @param wordDict, a set<string>
    # @return a boolean
    def wordBreak(self, s, wordDict):
        size = len(s)
        dp = [False] * size
        
        for i in range(size):
            for j in range(i+1, size+1):
                if s[i:j] not in wordDict:
                    continue
                if i == 0 or (i > 0 and dp[i-1]):
                    dp[j-1] = True
        return dp[size-1]

Log in to reply
 

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