Word Break

Given a string and a dictionary, determine if the string can be segmented into a space-separated sequence of dictionary words. Brute-force recursion tries all splits and is exponential.

Why this is worth learning

A dictionary word is an edge between two prefix boundaries. The task is reachability from boundary 0 to boundary len(s), not greedy longest-word selection.

Before coding: one-minute experiment

For s="cars" and dictionary ["car","ca","rs"], why does choosing the longest initial word fail while DP succeeds?

Function signature

func WordBreak(s string, wordDict []string) bool

Inputs / outputs

• s: input string.
• wordDict: list of valid words.
• Return: true if s can be segmented.

Example

s = "leetcode", dict = ["leet","code"] -> true
s = "catsandog", dict = ["cats","dog","sand","and","cat"] -> false

Constraints

• 0 <= len(s) <= 300
• 1 <= len(wordDict) <= 1_000

Core idea (near-solution)

DP over prefixes: dp[i] is true if s[:i] can be segmented. Only check split points within the max word length.

Invariant: dp[i] reflects whether any valid split ends at i.

Algorithm (step-by-step)

1. Put dictionary words in a set and compute maxLen.
2. Initialize dp[0]=true.
3. For i from 1..n:
   • For j from max(0, i-maxLen) to i-1:
     • If dp[j] and s[j:i] in set, set dp[i]=true and break.
4. Return dp[n].

Correctness sketch

Let dp[i] mean that exactly s[:i] can be segmented into dictionary words. The empty prefix is reachable by taking no words. Any nonempty valid segmentation has a final word s[j:i] and a segmentable preceding prefix, so it implies dp[j] and dictionary membership. Conversely those two facts concatenate into a valid segmentation of s[:i]. Testing all j within the maximum dictionary word length is exhaustive because longer suffixes cannot be words. Induction in increasing i computes reachability at every boundary and hence the answer.

Trace (hand walkthrough)

Example input:
s = "leetcode", dict = ["leet","code"] -> true
s = "catsandog", dict = ["cats","dog","sand","and","cat"] -> false

Walk:
- "leetcode": dp[4]=true (leet), dp[8]=true (code) -> true
- "catsandog": dp[3]=true (cat), dp[4]=true (cats), dp[7]=true (sand/and) but dp[9]=false -> false

Pitfalls to avoid

• Off-by-one in dp sizing (needs n+1).
• Scanning all j without limiting by maxLen.
• Treating empty string as false (dp[0] should be true).

Debugging lens

Test empty input, reusable words, a segmentable prefix with an impossible final byte, and overlapping dictionary prefixes. String slicing is cheap, but hashing a newly queried substring still reads its bytes.

Complexity

Let n be len(s), L the longest dictionary word length capped at n, W the number of dictionary entries, and D their total byte length. Expected O(D + n*L²) time for the supplied substring-hash-map implementation, because up to L candidate substrings per endpoint each cost up to O(L) bytes to hash. O(n+W) additional state/map entries, excluding already-owned string payload; dictionary payload retained by keys is at most O(D).

Implementation notes (Go)

• Use a map[string]bool as a set.
• Substring slicing s[j:i] creates a constant-size header without copying bytes, but a map lookup hashes the candidate bytes. Include that length-dependent work in the stated complexity.

Contract precision

Matching uses byte-exact Go strings. The empty input returns true because it has an empty segmentation; empty dictionary entries do not advance any boundary.

Reconstruction checkpoint

For s="cars" and dictionary ["car","ca","rs"], why does choosing the longest initial word fail while DP succeeds?

Return to 1D DP (Including Kadane) · Module quiz