Python DP solution


  • 0
    G
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a boolean
        def wordBreak(self, s, dict):
            if not dict:
                return False
            
            d = [False] * len(s)
            
            for i in range(len(s)):
                for w in dict:
                    if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) is -1):
                        d[i] = True
            
            return d[-1]

  • 0
    H

    If dict is huge. this method will be very slow


Log in to reply
 

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