Word Break LeetCode Solution — Complete DP Walkthrough

Word Break (LeetCode #139) sits at the intersection of dynamic programming and string manipulation, making it one of the most frequently asked medium problems at Google, Amazon, and Meta. Unlike classic DP problems that operate on arrays of numbers, Word Break forces you to think about how DP applies to strings — a skill that catches many candidates off guard.

The problem is deceptively simple to state: given a string s and a dictionary of words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. For example, given s = "leetcode" and wordDict = ["leet", "code"], the answer is true because "leetcode" can be segmented as "leet code".

What makes this word break leetcode problem so popular in interviews is that it has multiple valid approaches — recursive memoization, bottom-up DP, and even BFS — each revealing different aspects of your problem-solving ability. In this walkthrough, we will cover all three approaches with full complexity analysis so you can pick the one that feels most natural during your interview.

Before jumping into solutions, let us make sure the problem statement is crystal clear. You are given a non-empty string s and a list wordDict containing a list of non-empty words. You need to determine if s can be segmented into a space-separated sequence of one or more dictionary words. The same word in the dictionary may be reused multiple times in the segmentation.

Consider s = "applepenapple" with wordDict = ["apple", "pen"]. The answer is true because you can segment it as "apple pen apple". Note that "apple" is reused — the dictionary is not consumed. Now consider s = "catsandog" with wordDict = ["cats", "dog", "sand", "and", "cat"]. The answer is false — no valid segmentation exists despite multiple partial matches.

The key insight for the word break dp approach is recognizing that this is an optimization problem in disguise. At each position in the string, you are asking: does any word in my dictionary match a prefix starting here? If yes, can I solve the remaining suffix? This overlapping subproblem structure is exactly what makes dynamic programming the right tool.

The most intuitive approach to the word break problem starts with recursion. Define a function canBreak(start) that returns true if the substring s[start..n-1] can be segmented using dictionary words. The base case is simple: if start equals the string length, we have successfully segmented everything, so return true.

For each call to canBreak(start), iterate through every word in the dictionary. If the word matches s starting at position start (i.e., s.substring(start, start + word.length) equals the word), then recursively check canBreak(start + word.length). If any recursive call returns true, the current call returns true.

Without memoization, this approach has exponential time complexity because the same start index gets recomputed many times. Adding a memo array that caches the result for each start index reduces the time complexity to O(n * m * k) where n is the string length, m is the dictionary size, and k is the average word length for substring comparison. Space complexity is O(n) for the memo array plus O(n) for the recursion stack.

This leetcode 139 solution is often the first approach candidates think of, and interviewers appreciate seeing the natural progression from brute-force recursion to memoized recursion. It demonstrates that you understand overlapping subproblems — the hallmark of dynamic programming string problems.

The bottom-up approach eliminates recursion entirely. Create a boolean array dp of size n+1, where dp[i] means the substring s[0..i-1] can be segmented into dictionary words. Initialize dp[0] = true because an empty string is trivially segmentable.

For each position i from 1 to n, check every position j from 0 to i-1. If dp[j] is true and the substring s[j..i-1] exists in the dictionary, then set dp[i] = true. The answer is dp[n]. Converting the dictionary to a Set gives O(1) lookup, which is critical for performance.

The time complexity of this word break dp solution is O(n^2 * k) where n is the string length and k is the average substring length for hashing. The space complexity is O(n) for the dp array plus O(m * k) for the word set. This is the approach most interviewers expect to see, and it is clean enough to code in under ten minutes.

One practical optimization: instead of checking all j from 0 to i-1, you only need to check substrings whose length matches a word in the dictionary. Track the maximum word length maxLen and only check j values where i - j is between 1 and maxLen. This prunes the inner loop significantly when the dictionary contains short words but the string is long.

Here is a perspective that surprises many candidates: Word Break can be modeled as a graph problem. Think of each index in the string as a node. There is a directed edge from index i to index j if s[i..j-1] is a word in the dictionary. The question becomes: is there a path from node 0 to node n?

Using BFS, start with index 0 in the queue. For each index you dequeue, try every word in the dictionary. If the word matches starting at that index, add the end index to the queue. If you ever reach index n, return true. Use a visited set to avoid processing the same index twice.

The word break BFS approach has the same time complexity as the DP solution — O(n * m * k) — but it can be faster in practice for certain inputs because it explores promising paths first and can terminate early. It also avoids the overhead of filling the entire DP table when the answer is true and reachable through a short path.

This approach is particularly valuable in interviews because it demonstrates versatility. If the interviewer has already seen ten candidates present the DP solution, showing the BFS perspective makes you memorable. It also naturally extends to Word Break II where you need to find all valid segmentations.

Before submitting your solution, consider these edge cases that trip up candidates. An empty string should return true (it is trivially segmentable). A single character string requires checking if that character exists as a word in the dictionary. A string where no dictionary word appears as a substring should return false immediately.

Watch out for repeated characters: s = "aaaaaaa" with wordDict = ["aaaa", "aaa"] returns true because 3 + 4 = 7. Greedy approaches fail here — if you greedily match "aaaa" first, you are left with "aaa" which works, but if you match "aaa" first you get "aaaa" which also works. However, s = "aaaaaaa" with wordDict = ["aaaa", "aa"] returns false because you cannot make 7 from 4s and 2s.

The natural follow-up is Word Break II (LeetCode #140), a Hard problem that asks you to return all possible segmentations rather than just whether one exists. This requires backtracking on top of DP — first use the DP table to verify segmentation is possible, then backtrack to collect all valid paths. Do not attempt this dynamic programming string variant until you have the basic version down cold.

Word Break is one of the best problems for building intuition about dynamic programming on strings. Most DP problems candidates study involve arrays of numbers — Climbing Stairs, House Robber, Coin Change. Word Break forces you to transfer that same DP mindset to string segmentation, which is a fundamentally different shape of problem.

The core lesson is that DP state does not have to be about "which element am I at" — it can be "which position in the string have I segmented up to." This same state definition appears in other string DP problems like Palindrome Partitioning, Decode Ways, and Concatenated Words. Once you internalize this pattern, an entire class of problems opens up.

Converting the dictionary to a Set for O(1) lookup is another transferable technique. Many string problems involve checking membership in a collection, and candidates who reach for arrays or linear scans leave performance on the table. Always ask yourself: can I preprocess this collection into a hash-based structure?

To truly master the word break leetcode pattern, you need to practice it until recognition is instant. YeetCode flashcards help you drill exactly this — not memorizing code, but recognizing that a string segmentation problem calls for DP with a boolean array indexed by position. Review the pattern, recall the approach, and build the muscle memory that makes interview day feel like practice.