Super easy DFS memoization Python Solution

  • 1
    def wordBreak(self, s, wordDict):
        :type s: str    
        :type wordDict: Set[str]
        :rtype: bool
        if s in self.mem:
            return self.mem[s]
        size = len(s)
        if size == 0:
            return True
        for prefix in wordDict:
            length = len(prefix)
            if s[0:length] == prefix and self.wordBreak(s[length:], wordDict):
                self.mem[s] = True
                return True
        self.mem[s] = False            
        return False

    The intuition is easy. Just check whether the string is prefixed with the current word in dictionary or not, if yes go deeper and check if the substring (without the prefix) can be broken into words in dict. Otherwise, try next word in the dictionary.

    Use memoization because there is a lot of repetition.

  • 0

    @gnetgnol return wrong answer to input "a", ["a"]

Log in to reply

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