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.

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

• Invariant: dp[i] reflects whether any valid split ends at i.
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct 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).

Complexity

• Time: O(n * maxLen).
• Extra space: O(n).

Implementation notes (Go)

• Use a map[string]bool as a set.
• Substring slicing s[j:i] is O(1) in Go (no copy), but still ok.