Python 42ms DP recursive solution


  • 0
    O

    The iteration is on the item of wordDict. A dictionary d is added to reduce the calculation. The parameter k records the index of s.

        def wordBreak(self, s, wordDict):
            d = {}
            def f(S,k):
                if k in d:return d[k]
                if not S:return True
                for w in wordDict:
                    n = len(w)
                    if S[0:n]==w:
                        d[k]=f(S[n:],k+n)
                        if d[k]:return True
                d[k]=False
                return False
            return f(s,0)
    

    My first code got TLE (for not put d into it), but it is easier to understand:

        def wordBreak(self, s, wordDict):
            def f(S):
                if not S:return True
                for w in wordDict:
                    n = len(w)
                    if S[0:n]==w and f(S[n:]):return True
                return False
            return f(s)
    

Log in to reply
 

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