Word Break II

Dynamic Programming
Hard

Approach

Diagrams

Analysis

Time

Space

class Solution:
    def wordBreak(self, string, wordDict):
        return self.dfs(string, wordDict, {})

    def dfs(self, string, wordDict, memo):
        if not string:
            return

        if string in memo:
            return memo[string]

        possibleSentences = []

        for word in wordDict:
            wordIsNotPrefix = not string.startswith(word)
            if wordIsNotPrefix:
                continue

            wordIsFullMatch = len(word) == len(string)
            if wordIsFullMatch:
                possibleSentences.append(word)

            else:
                unmatchedPartOfString = string[len(word):]
                partialSentencesFromUnmatchedPartOfString = self.dfs(unmatchedPartOfString, wordDict, memo)

                for partialSentence in partialSentencesFromUnmatchedPartOfString:
                    possibleSentence = word + ' ' + partialSentence
                    possibleSentences.append(possibleSentence)

        memo[string] = possibleSentences
        return possibleSentences

Learn

#Memoization

#Dynamic Programming

Videos