Top-down with memoization method in Python


  • 0
    L
    class Solution:
        # @param s, a string
        # @param dict, a set of string
        # @return a boolean
    
        def wordBreak(self, s, dict):
            dict = set(dict)
            start = 0
            end = len(s)-1
            memo = {}
            return self._wordBreak(s, dict, start, end, memo)
            
        def _wordBreak(self, s, dict, start, end, memo):
            if s[start:end+1] in memo:
                return memo[s[start:end+1]]
            elif s[start:end+1] in dict:
                memo[s[start:end+1]] = True
                return True
            for i in xrange(start, end):
                if s[start:i+1] in dict and self._wordBreak(s, dict, i+1, end, memo):
                    return True
            memo[s[start:end+1]] = False
            return False
    

    maybe top-down method is easy to understand.


Log in to reply
 

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