Super easy DFS memoization Python Solution


  • 1
    G
    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
    C

    @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.