Loading problem…
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Example 1
Input: s = bookcase, wordDict = ["book","case"]
Output: true
Explanation: "bookcase" splits into "book" + "case", and both are dictionary words.
Example 2
Input: s = applepenapple, wordDict = ["apple","pen"]
Output: true
Explanation: "applepenapple" splits into "apple pen apple". Dictionary words may be reused, so "apple" can appear twice.
Example 3
Input: s = catsandog, wordDict = ["cats","dog","sand","and","cat"]
Output: false
Explanation: "catsandog" can start as "cats and" or "cat sand", but both leave "og", which is not a dictionary word. So it cannot be fully segmented.
Define `dp[i]` = `True` iff the prefix `s[:i]` can be segmented into dictionary words. The last word in any valid segmentation ends at position `i`, so it starts at some earlier position `j` where `dp[j]` was already `True` and `s[j:i]` is a dictionary word. Try every split point.
Run checks all cases above. Submit evaluates all test cases.