#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/dynamic-programming-1d/word-break-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/pattern-22/dynamic-programming-1d/word-break-implementation

Repovive

LeetCode 139 Word Break - Implementation - Dynamic Programming - 1D | Pattern 22: LeetCode Interview Patterns | Repovive

Repovive.

Pattern 22: LeetCode Interview Patterns24 sections · 736 units32h total

Open in Course

LeetCode 139 Word Break - Implementation

The approach

DP with dictionary lookup. Check all possible last words.

def wordBreak(s, wordDict): wordSet = set(wordDict) n = len(s) dp = [False] * (n + 1) dp[0] = True

for i in range(1, n + 1):
    for j in range(i):
        if dp[j] and s[j:i] in wordSet:
            dp[i] = True
            break

return dp[n]

$O(n^2)$ time (with hash set lookup), $O(n)$ space.