Watch 10 video solutions for Word Break, a medium level problem involving Array, Hash Table, String. This walkthrough by NeetCode has 345,872 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |