Word break

Problem Given a string s and a word dictionary, determine whether s can be segmented into a sequence of one or more dictionary words (words reusable).

Input / Output

• Input: string s, list wordDict.
• Output: boolean.

Constraints

• |s| up to 300, dictionary up to 1000 words — O(n^2) DP with a word set is intended; plain recursion is exponential.

Example

• s = "applepenapple", dict = ["apple","pen"] → true; s = "catsandog", dict = ["cats","dog","sand","and","cat"] → false.

Expected approach

• DP: dp[i] = s[0..i) segmentable; dp[0] = true; dp[i] = OR over j < i of (dp[j] AND s[j..i) ∈ wordSet); bound j by the max word length to tighten. O(n^2). Equivalent top-down memoized DFS. Follow-on: Word Break II (return all segmentations — backtracking + memo) is the standard escalation; know why II can blow up exponentially.