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.
Example 1:
Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code".
Example 2:
Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.
Example 3:
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false
Constraints:
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.wordDict are unique.The Word Break problem asks whether a string can be segmented into valid words from a given dictionary. A common strategy is to treat it as a dynamic programming problem where we check if prefixes of the string can be formed using dictionary words. Create a boolean dp array where dp[i] indicates whether the substring up to index i can be segmented. For each position, check previous valid splits and verify if the current substring exists in a hash set of dictionary words.
Another efficient variation combines DFS with memoization or a Trie to quickly check valid prefixes while avoiding repeated computations. Memoization stores results of previously checked substrings, significantly reducing redundant work. These techniques help transform an exponential brute-force search into a more efficient solution suitable for interview settings.
Typical implementations achieve around O(n^2) time depending on substring checks, with additional space used for DP or memoization structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Hash Set | O(n^2) | O(n) |
| DFS with Memoization | O(n^2) | O(n) |
| Trie + Backtracking | O(n^2) | O(n + m) |
NeetCode
Dynamic Programming is a common approach for problems involving finding solutions over mutable subsets of an input set. We can use a boolean array 'dp' with length 'n+1', where 'n' is the length of the input string 's'. 'dp[i]' will indicate whether the substring 's[0...i-1]' can be segmented into words from the dictionary. We initialize 'dp[0]' to true since an empty substring can always be segmented.
For each position 'i' from 1 to n, iterate through each previous position 'j' from 0 to i-1, and check if the substring 's[j:i]' is in the word dictionary and if 'dp[j]' is true. If both conditions are met, set 'dp[i]' to true and break out of the loop.
The final answer will be found in 'dp[n]'.
Time Complexity: O(n^2 * m), where n is the length of the string and m is the size of the dictionary. Each substring check requires a loop over the dictionary.
Space Complexity: O(n) for the dp array.
1var wordBreak = function(s, wordDict) {
2 const wordSet = new Set(wordDict);
3 const dp
The JavaScript solution uses an array 'dp' to track the validity of substrings and a Set for fast dictionary lookups. The core logic follows nested loops iterating over possible substrings.
This approach utilizes Depth First Search (DFS) with the help of memoization to avoid redundant work. By storing the results of overlaps in a memoization structure, we cut down unnecessary recalculations. The recursive function attempts to segment the string from an index 'start' and uses a hash set for quick lookups of dictionary words. The function operates recursively trying to partition the string and caches results for indices already computed, preventing repetitions of partial solutions.
Time Complexity: O(n^2) in the worst case due to substring check overhead between start and end.
Space Complexity: O(n) for the memo array storage.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Word Break is a classic dynamic programming interview question frequently asked in FAANG and other top tech companies. It tests understanding of DP, recursion with memoization, and efficient string processing.
Memoization stores the results of previously computed substrings so they are not recomputed again. This avoids redundant recursion and significantly improves performance compared to pure backtracking.
The most common optimal approach uses dynamic programming with a hash set for quick dictionary lookups. A dp array tracks whether prefixes of the string can be segmented. This reduces the exponential brute-force search to roughly O(n^2) time.
A hash set is typically used to store dictionary words for O(1) average lookup. In some optimized solutions, a Trie can also be used to efficiently match prefixes and reduce repeated substring checks.
This Java solution involves a DFS approach with memoization stored in a HashMap. It recursively processes substrings from the start index, storing results to avoid recomputation.