Asked at
Word Break
MediumVerifiedTrieDynamic ProgrammingString~25 min
Given a string s and a dictionary wordDict, return true if s can be segmented into a sequence of dictionary words.
Words may repeat. A DP flag at each index marks whether the prefix up to there is segmentable.
The input arrives as a single object { s, wordDict }.
Examples
in{ s: "leetcode", wordDict: ["leet", "code"] }
outtrue
"leetcode" splits into "leet" + "code".
in{ s: "catsandog", wordDict: ["cats", "dog", "sand", "and", "cat"] }
outfalse
No segmentation covers the whole string.
Constraints
- 1 ≤ s.length ≤ 300
- 1 ≤ wordDict.length ≤ 1000
- All strings consist of lowercase English letters.
Get help
🔑
Sign in to solve
Sign in to write, run, and submit your solution — and to pick up where your iOS flow left off.