Word Break
Module 24 · Dynamic Programming
Problem
Given a string s and a dictionary of strings wordDict, return true
if s can be segmented into a space-separated sequence of one or more
dictionary words. Words may be reused any number of times.
(LeetCode 139.)
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]OutputtrueExplanation. leet" + "code
Example 2
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]OutputfalseConstraints
1 ≤ s.length ≤ 300, up to1000dictionary words.
Attempt it first
This has the exact same "try every split point" shape as Palindrome
Partitioning (Module 16) — but that problem needed EVERY valid
partitioning (backtracking, necessarily exploring many branches), while
this one only needs a single yes/no answer. Before opening anything,
think about why that difference — ALL partitionings vs. JUST
reachability — is precisely what makes DP applicable here where
Module 16 used backtracking, and define dp[i] = "can the prefix
s[0:i] be fully segmented using dictionary words."