Dynamic Programming · 037Medium
Word Break
Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Words may be reused.
Constraints
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- All dictionary words are unique and lowercase.
Examples
wordBreak("leetcode", ["leet", "code"]) -> true
wordBreak("applepenapple", ["apple", "pen"]) -> true // reuse allowed
wordBreak("catsandog", ["cats","dog","sand","and","cat"]) -> false
wordBreak("a", ["a"]) -> true // shortest possible input
wordBreak("a", ["b"]) -> false // no word matches
wordBreak("aaaaaaa", ["aaaa", "aaa"]) -> true // 4 + 3Edge cases
- Words may be reused any number of times.
Show the target complexity (spoiler)
- Naive
- O(2^n) time — recurse on every split point without memoisation.
- Target
- O(n^2 * m) time, O(n) space — dp[i] is true if some j < i has dp[j] true and s[j..i) is in the dictionary.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/09-dynamic-programming/037-word-break.js ./practice c 037