DSA problem
Word Break
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. Note that the same word in the dictionary may be reused multiple times in the segmentation.
The brute force tries every possible split of s at every index, leading to exponential blow-up because the same suffix is solved repeatedly. Memoization or bottom-up tabulation collapses the overlapping subproblems into polynomial time.
Define dp[i] as a boolean meaning "the prefix s[0..i) can be segmented into dictionary words". Base case dp[0] = true because the empty string is trivially segmented. Transition: dp[i] is true iff there exists some j < i with dp[j] = true AND s[j..i) appears in the dictionary. Convert the dictionary to a hash set for O(1) membership checks.
The optimal time is O(n^2 * L) where L is the maximum word length (substring slicing/hashing costs L). To avoid redundant checks, you can cap the inner loop at the maximum word length in the dictionary, which significantly tightens the constant factor. Space is O(n) for the dp array plus O(W) for the set of dictionary words.
Examples
s = "leetcode", wordDict = ["leet","code"]trues = "applepenapple", wordDict = ["apple","pen"]trues = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falseConstraints
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s and wordDict[i] consist of only lowercase English letters.
- All the strings of wordDict are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.