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.