Word Break

LeetCode 139 • Medium • Dynamic Programming

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.

TimeO(n²·k)n=|s|, k=word len

SpaceO(n)dp

Step0/0

s = "leetcode" dict = { leet, code }

Ready

dp[i] = can segment s[0:i] (first i chars). Empty string is reachable: dp[0]=true.

Speed:

✎ Whiteboard

Size:3

⌨ Type It

═══ DP ═══

words = set(wordDict)

dp[0] = True

for i in range(1, len(s)+1):

for j in range(i):

if dp[j] and s[j:i] in words: dp[i]=True

Verify:

⌨ Type It — DFS

Verify: