Top-down with memoization method in Python

  • 0
    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.