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.Problem Overview: You receive a string s and a dictionary of valid words. The task is to determine whether the string can be segmented into a sequence of one or more dictionary words. Each word in the dictionary can be reused multiple times.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
This approach uses dynamic programming to track which prefixes of the string can be segmented successfully. Create a boolean array dp where dp[i] indicates whether the substring s[0..i) can be formed using dictionary words. Iterate through the string and for each index i, check all previous split points j. If dp[j] is true and the substring s[j:i] exists in a dictionary set, mark dp[i] as true. Using a hash table for dictionary lookup keeps substring checks constant time on average. The key insight is building valid solutions for larger prefixes from previously validated smaller prefixes.
Approach 2: Memoization-based Depth First Search (O(n^2) time, O(n) space)
This method treats the problem as recursive exploration of all possible prefixes. Starting from index 0, attempt to match every dictionary word as a prefix of the remaining substring. If a prefix matches, recursively attempt to segment the rest of the string. Without optimization this becomes exponential, so memoization stores results for previously processed starting indices. When recursion revisits the same index, the cached result avoids redundant work. This pattern combines recursion with memoization to prune the search tree efficiently.
Conceptually, the recursion explores the segmentation tree while memoization collapses repeated subproblems. Each index in the string is processed at most once after caching, giving a practical time complexity close to O(n^2) due to substring checks.
Recommended for interviews: The bottom-up dynamic programming solution is the most commonly expected answer. It clearly demonstrates understanding of substring partitioning and state transitions. Interviewers often accept the memoized DFS as well because it shows strong recursion reasoning and awareness of overlapping subproblems. Starting with the recursive idea and then optimizing it with memoization or converting it to DP demonstrates strong problem-solving progression.
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]'.
This C solution involves two key functions: 'wordBreak' and 'validSubstring'. We first initialize a DP array of size n+1 and set dp[0] to true. For every substring of s (from j to i), we check if it exists in the dictionary using 'validSubstring'. If an entry exists and dp[j] is true, we set dp[i] to true. The function ends by returning dp[n], which indicates the segmental validity of the entire string.
C++
Java
Python
C#
JavaScript
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.
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.
This C solution uses a helper function 'wordBreakUtil' which applies DFS recursively with memoization to store results of overlapping subproblems. The main function initializes a memoization array and calls the utility function for processing.
C++
Java
Python
C#
JavaScript
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.
| Approach | Complexity |
|---|---|
| Approach 1: Dynamic Programming | 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. |
| Approach 2: Memoization-based Depth First Search | Time Complexity: O(n^2) in the worst case due to substring check overhead between start and end. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming | O(n^2) | O(n) | Best general solution for interviews and large inputs |
| DFS with Memoization | O(n^2) | O(n) | Good when reasoning recursively about prefix choices |
Word Break - Dynamic Programming - Leetcode 139 - Python • NeetCode • 345,872 views views
Watch 9 more video solutions →Practice Word Break with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor