python easy to understand recursive solution with memorization


  • 0
    W
    class Solution(object):
        def __init__(self):
            self.cache = set()
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: bool
            """
            if s in self.cache:return False
            if s in wordDict:return True
            for i in xrange(1,len(s)):
                if s[:i] in wordDict and self.wordBreak(s[i:],wordDict):
                    return True
            self.cache.add(s)
            return False
    

Log in to reply
 

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