Word Break
Can s be segmented into a sequence of dictionary words? (The backtracking variant prints every segmentation.)
Intuition
Whether the suffix starting at i is breakable doesn't depend on how you got to i — perfect memoization target. dp[i] = true if some dictionary word starts at i and dp[i + len(word)] holds.
String-partition DP: dp[i] asks whether the suffix starting at i can be segmented. Every cut point is a subproblem, and the answer chains right-to-left. Reach for this whenever a string must be split into pieces drawn from a set — palindrome partitioning and word-break II share the skeleton.
Approach
Naive recursion repeats suffixes
Trying every prefix word and recursing re-solves the same suffix exponentially many times.
DP over positions
dp[n] = True (empty suffix). Going right to left, dp[i] = any(s.startswith(w, i) and dp[i+len(w)]). Answer dp[0].
Printing all ways
Keep the same recursion but collect paths, memoizing suffix → list of segmentations to avoid recomputation.
Solution & live demo
Common pitfalls
Greedily taking the longest matching prefix
while s:
for w in sorted(words, key=len, reverse=True):
if s.startswith(w):
s = s[len(w):]
breakfor i in range(n - 1, -1, -1):
for j in range(i + 1, n + 1):
if s[i:j] in words and dp[j]:
dp[i] = True; breakOn s = "aaaaab" with words ["aaaa", "aaa", "b"], taking the longest first strands the rest. A wrong early cut can only be discovered later, so every cut point has to stay on the table.
Leaving dp[n] false
dp = [False] * (n + 1)
dp = [False] * (n + 1) dp[n] = True
dp[n] represents the empty suffix, which is trivially segmentable — it's the base case every chain terminates in. Without it no dp[i] can ever become true and the answer is always false.
Keeping wordDict as a list
if s[i:j] in wordDict:
words = set(wordDict) if s[i:j] in words:
Membership in a list is a linear scan, so the inner test becomes O(m) and the whole solution O(n²·m). A set makes it O(1) — a one-line change that dominates the runtime.
Edge cases
Dictionary words are reusable — dp naturally allows it.
dp explores every word start, not just greedy longest.