Word Break
Medium· 1D DP· string
Problem
Given a string and a list of dictionary words, decide whether the string can be split into a sequence of one or more dictionary words. Words may be reused any number of times.
Examples
Input: s = "leetcode", wordDict = ["leet","code"]
Output: true
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: false
Constraints
- • 1 <= s.length <= 300
- • 1 <= wordDict.length <= 1000
- • All dictionary words are distinct
Hints & approach
Hint 1
If a prefix can be segmented, what must be true about the rest?
Hint 2
Track which prefix lengths can be fully segmented.
Hint 3
ok[i] is true if some j < i has ok[j] true and s[j..i) is a dictionary word.
Approachtry the hints first
Put the dictionary in a hash set. Let ok[i] mean the first i characters can be segmented, with ok[0] = true. For each i, look for a split point j where ok[j] is true and the substring s[j..i) is in the set. Limiting j to within the longest word length of i keeps it fast. The answer is ok[n].
Time O(n²) substring checks · Space O(n)