Dynamic Programming
LC #139Medium
Word Break
Dynamic Programming
AmazonGoogleMetaBloombergMicrosoftProblem
Determine if a string can be segmented into words from a dictionary.
stringdynamic-programmingtrie
Constraints
- ›1 ≤ s.length ≤ 300
- ›1 ≤ wordDict.length ≤ 1000
- ›1 ≤ wordDict[i].length ≤ 20
- ›Lowercase English only; no duplicate words
Example
Input
s = "leetcode", wordDict = ["leet","code"]Output
trueWhy
"leetcode" = "leet" + "code". Both words in dictionary