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 get a string s and a dictionary of valid words. The task is to determine if s can be split into a sequence of one or more dictionary words. Words can be reused, and segmentation must cover the entire string.
Approach 1: Dynamic Programming (O(n^2) time, O(n) space)
This approach treats the problem as a prefix segmentation check using dynamic programming. Create a boolean array dp where dp[i] means the substring s[0..i-1] can be formed using words from the dictionary. Convert the word list into a hash set for O(1) membership checks using a hash table. Iterate over every end index i, then scan earlier split points j. If dp[j] is true and s[j:i] exists in the dictionary, mark dp[i] as true. The key insight: if a valid segmentation exists up to position j, and the remaining substring is a dictionary word, the prefix ending at i is also valid. This bottom‑up method avoids recomputation and runs in O(n^2) time with O(n) space.
Approach 2: Memoization-based Depth First Search (O(n^2) time, O(n) space)
This strategy explores segmentations recursively using DFS combined with memoization. Start from index 0 and attempt every possible prefix that appears in the dictionary. When a valid prefix is found, recursively check the remaining suffix. Without caching, this produces exponential recursion because the same substring gets recomputed many times. Memoization fixes that by storing whether a starting index can eventually form a valid segmentation. Each index is evaluated once, and each check performs substring and dictionary lookups, resulting in roughly O(n^2) time. Space usage is O(n) for the recursion stack and memo table.
DFS with memoization is often easier to reason about because it mirrors the natural “try every word prefix” thought process. However, the bottom‑up DP version usually performs better in interviews because it avoids recursion overhead and makes the state transition explicit.
Recommended for interviews: The dynamic programming solution is the most commonly expected answer. It demonstrates strong understanding of prefix-based DP states and efficient substring validation with a hash set. Mentioning the recursive DFS first shows you understand the brute-force search space, then optimizing it with memoization or converting it to bottom-up DP shows problem-solving maturity.
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.
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.
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. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Bottom-Up) | O(n^2) | O(n) | Best general solution for interviews; avoids recursion and clearly models prefix segmentation. |
| DFS with Memoization | O(n^2) | O(n) | Useful when thinking recursively about prefixes; easier to derive from brute-force search. |
Word Break - Dynamic Programming - Leetcode 139 - Python • NeetCode • 424,268 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