LeetCode 139 Word Break - Implementation

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.