Easy understand Python DP solution

  • 4
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a boolean
        def wordBreak(self, s, dict):
            n = len(s)
            f = [False for i in range(n+1)]
            f[0] = True
            for i in range(n):
                if f[i]:
                    for j in dict:
                        l = len(j)
                        if i+l<=n and s[i:i+l] == j:
                            f[i+l] = True
            return f[n]

Log in to reply

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