Skip to main content
Talentd

Word Break - Solution & Explanation

MediumArrayHash TableStringDynamic Programming17 min readAsked at: Amazon, Microsoft, Apple +29
Practice this problem

Problem Statement

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 <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s and wordDict[i] consist of only lowercase English letters.
  • All the strings of wordDict are unique.

Approach Overview

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 1: Approach 1: Dynamic Programming

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Memoization-based Depth First Search

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) for the dp array.

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.
Space Complexity: O(n) for the memo array storage.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 MemoizationO(n^2)O(n)Useful when thinking recursively about prefixes; easier to derive from brute-force search.

Video Solution

Word Break - Dynamic Programming - Leetcode 139 - Python • NeetCode • 442,280 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Word Break easy or hard?
Word Break is considered a medium difficulty problem. The challenge is recognizing that brute-force recursion leads to exponential complexity and converting that idea into dynamic programming or memoization.
How to solve Word Break in O(n)?
A strict O(n) solution is generally not achievable because every position may need to check multiple earlier split points. The practical optimal solution is O(n^2) using dynamic programming or DFS with memoization and a hash set for dictionary lookups.
What is the best approach for Word Break?
The dynamic programming approach is the most common solution. Use a boolean DP array where dp[i] represents whether the prefix ending at index i can be segmented using dictionary words. With a hash set for fast lookups, the algorithm runs in O(n^2) time and O(n) space.
What data structure is used in Word Break?
The solution typically uses a hash set to store dictionary words for O(1) membership checks and a dynamic programming array to track valid segmentations. Some optimized implementations also use a Trie to speed up prefix matching.
What is the time complexity of Word Break?
Both the optimized dynamic programming and memoized DFS solutions typically run in O(n^2) time, where n is the string length. Each position checks earlier split points and performs constant-time dictionary lookups using a hash set. Space complexity is O(n) for the DP array or memo cache.
Word Break Python or Java solution approach?
Python and Java implementations usually follow the same dynamic programming pattern: convert the dictionary to a set, iterate through string indices, and check valid split points. Both achieve O(n^2) time and O(n) space complexity.
Is Word Break asked at Google or Amazon interviews?
Word Break is a classic dynamic programming interview problem and appears frequently in coding interviews at companies like Amazon, Google, and Meta. Variants include returning all valid sentences (Word Break II) or optimizing with a Trie.

Ready to solve this problem?

Practice Word Break with our built-in code editor and test cases.

Practice on FleetCode
Previous

Extra Characters in a String

Next

Word Break II