Python with additional logic to determine number of different ways a word can be broken


  • 0
    B

    in addition to determining if a word can be broken this function can also return number of different ways it can be broken. Time complexity O(mn) n = len(s), m=len(wordDict)

    class Solution(object):
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: List[str]
            :rtype: bool
            """
            if len(s) < 1 or len(wordDict) < 1: return None
            self.memo = {}
            self.cnt = 0
            self.helper(s, wordDict)
            return True if self.cnt else False
    
        def helper(self, s, wordDict):
            for word in wordDict:
                    if s == "" : 
                            self.cnt += 1
                            return True
                    if not s.startswith(word):
                            continue
                    else: 
                            if word+'-'+s in self.memo:
                                    if self.memo[word+'-'+s]: self.cnt += 1
                                    return self.memo[word+'-'+s]
                            retVal = self.helper(s[len(word):],wordDict)
                            if retVal: 
                                    self.memo[word+'-'+s] = True
                            else:
                                    self.memo[word+'-'+s] = False
            return False
    

Log in to reply
 

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