Word Break

Dynamic Programming
Medium

Approach

Diagrams

Analysis

Time

O(n^3)

Space

O(n)
class Solution:
    def wordBreak(self, string, words):
        def dfs(path, memo):
            curString = ''.join(path)

            if len(curString) == len(string):
                nonlocal canBeSegmented
                canBeSegmented = True
                return

            if curString in memo:
                return

            for word in words:
                target = string[len(curString):]

                if target.startswith(word):
                    memo[curString] = True
                    path.append(word)
                    dfs(path, memo)
                    path.pop()

        canBeSegmented = False
        dfs([], {})
        return canBeSegmented

Learn

#Backtracking

Videos