Determine whether a string can be segmented into a sequence of dictionary words.
Word Break
Given a string s and a list of words wordDict, determine whether s can be formed by concatenating one or more words from the dictionary.
You may reuse dictionary words any number of times. The same dictionary word can appear multiple times in the segmentation if needed.
Your task is to return true if such a segmentation exists, otherwise return false.
Input Format
- A string
s - An array
wordDictof strings representing the dictionary
The exact input representation may vary by platform, but the logical inputs are always the same.
Output Format
Return a boolean value:
trueifscan be segmented into dictionary wordsfalseotherwise
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 1000- Dictionary words are non-empty strings
- Words may be reused multiple times
These are representative practice constraints, not guaranteed official limits.
Example 1
Input
s = "leetcode" wordDict = ["leet","code"]
Output
true
Explanation
"leetcode" can be split as "leet" + "code".
Example 2
Input
s = "applepenapple" wordDict = ["apple","pen"]
Output
true
Explanation
The string can be segmented as "apple" + "pen" + "apple".
Show 1 more example
Example 3
Input
s = "catsandog" wordDict = ["cats","dog","sand","and","cat"]
Output
false
Explanation
No valid segmentation covers the entire string.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.