My short python solution


  • 0
    B
    def wordBreak(self, s, wordDict):
        # initial elimination
        if s[-1] not in [x[-1] for x in wordDict]:
            return False
        return self.helper(0, 0, s, wordDict)
    
    def helper(self, start, end, s, wordDict):
        # initial elimination
        if s[start] not in [x[0] for x in wordDict]:
            return False
        
        while end < len(s) and s[start:end+1] not in wordDict:
            end += 1
        if end == len(s):
            return False
        elif end == len(s)-1:
            return True
        
        if not self.helper(end+1, end+1, s, wordDict):
            return self.helper(start, end+1, s, wordDict)
        else:
            return True

Log in to reply
 

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