Word Break
Medium · Dynamic Programming · String · Dynamic Programming · Trie · Memoization
Problem
Given a string s and a list of words wordDict, decide whether s can be built by concatenating one or more dictionary words. Words may be reused any number of times.
Examples
Input: s = "leetcode", wordDict = ["leet","code"] Output: True
"leet" + "code".
Input: s = "applepenapple", wordDict = ["apple","pen"] Output: True
"apple" is used twice.
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: False
Every greedy split dead-ends, which is why greedy is the wrong tool here.
Constraints
- 1 <= len(s) <= 300
- 1 <= len(wordDict) <= 1000
- 1 <= len(word) <= 20
- Words are unique
Approaches
- Top-down with memoisation — time O(n · L²), space O(n)
Related problems
Start free on Cariara · Coding problems · System design studio
