Given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given s = "leetcode" and wordDict = ["leet", "code"], return true because "leetcode" can be segmented as "leet code".
Explain your approach to solving this problem and state the time and space complexity.
How to approach it
- Hint 1
Think about whether each position in the string can be the end of a valid segmentation.
- Hint 2
Define dp[i] as whether the substring s[0..i-1] can be segmented using dictionary words.
- Hint 3
For each position i, check all positions j < i: if dp[j] is true and s[j..i-1] is in the dictionary, then dp[i] is true.
Ready to answer it out loud?
Record your answer in 1:30 and Preptile scores it 1–10 with specifics — what landed, what you skipped, and what to say next time.
Practising needs an invite code. Join the waitlist and we’ll send you one.