Approach Summary
dp[i] = true if s[0..i) can be segmented. For each i, check all j < i where dp[j] is true and s[j..i) is a word.
Practice Mode
2 Progressive Approaches
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Top-Down Memoized Search | O(n^2 * k) | O(n) memo + recursion stack | Recursively verify suffixes of s with a memoization cache tracking visited start indices. |
| 2 Approach 2: Bottom-Up Dynamic Programming (Optimal) | O(n^2 * k) | O(n) auxiliary | Tabulate prefix validity using dp[i] = dp[j] && s[j...i] in wordDict with early termination. |
Step 1: Baseline
Approach 1: Top-Down Memoized Search
Time: O(n^2 * k)
Space: O(n) memo + recursion stack
Define canBreak(start) which returns true if suffix s[start...] can be segmented. At each index, test every word in the dictionary that matches the prefix of s[start...]. If a match is found, recurse on start + len(word). Cache results in a boolean array to prevent re-evaluating invalid branches.
Approach 1: Top-Down Memoized Search Implementation
Approach 1: Top-Down Memoized Search
class Solution {
private boolean solve(String s, Set<String> dict, int start, Boolean[] memo) {
if (start == s.length()) return true;
if (memo[start] != null) return memo[start];
for (int end = start + 1; end <= s.length(); end++) {
if (dict.contains(s.substring(start, end)) && solve(s, dict, end, memo)) {
return memo[start] = true;
}
}
return memo[start] = false;
}
public boolean wordBreak(String s, List<String> wordDict) {
return solve(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
}
}class Solution {
public:
bool solve(string& s, unordered_set<string>& dict, int start, vector<int>& memo) {
if (start == s.size()) return true;
if (memo[start] != -1) return memo[start];
for (int end = start + 1; end <= s.size(); end++) {
if (dict.count(s.substr(start, end - start)) && solve(s, dict, end, memo)) {
return memo[start] = 1;
}
}
return memo[start] = 0;
}
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> dict(wordDict.begin(), wordDict.end());
vector<int> memo(s.size(), -1);
return solve(s, dict, 0, memo);
}
};class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
words = set(wordDict)
memo = {}
def can_break(start):
if start == len(s):
return True
if start in memo:
return memo[start]
for end in range(start + 1, len(s) + 1):
if s[start:end] in words and can_break(end):
memo[start] = True
return True
memo[start] = False
return False
return can_break(0)function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const memo = new Map();
function canBreak(start) {
if (start === s.length) return true;
if (memo.has(start)) return memo.get(start);
for (let end = start + 1; end <= s.length; end++) {
if (words.has(s.substring(start, end)) && canBreak(end)) {
memo.set(start, true);
return true;
}
}
memo.set(start, false);
return false;
}
return canBreak(0);
} Step 2: Most Optimized
Approach 2: Bottom-Up Dynamic Programming (Optimal)
Time: O(n^2 * k)
Space: O(n) auxiliary
Construct boolean array dp of size n + 1 with dp[0] = true. For each i from 1 to n, find any split j < i where dp[j] is true and substring s[j...i] is in dict. Once found, set dp[i] = true and break to the next i immediately.
Approach 2: Bottom-Up Dynamic Programming (Optimal) Implementation
Approach 2: Bottom-Up Dynamic Programming (Optimal)
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
Set<String> dict = new HashSet<>(wordDict);
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
}class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int n = s.size();
vector<bool> dp(n + 1, false);
dp[0] = true;
unordered_set<string> dict(wordDict.begin(), wordDict.end());
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && dict.find(s.substr(j, i - j)) != dict.end()) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
};class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
words = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in words:
dp[i] = True
break
return dp[n]function wordBreak(s, wordDict) {
const words = new Set(wordDict);
const n = s.length;
const dp = new Array(n + 1).fill(false);
dp[0] = true;
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && words.has(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}Edge Cases to Watch
- Single character matching dictionary word (e.g. s = "a", wordDict = ["a"])
- No segmentation possible (e.g. s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"])
- Overlapping prefixes (e.g. s = "cars", wordDict = ["car", "ca", "rs"])
- String where dictionary words must be reused multiple times (e.g. s = "applepenapple")
Algorithmic Pattern
View Pattern Guide →
Master the Dynamic Programming Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Dynamic Programming pattern.
Framework: Dynamic Programming • Interview Prep: Tested at FAANG •
Explore all Dynamic Programming problems & invariants →
How to Recognize This Pattern
- Can string be segmented using dictionary?
Complexity Analysis
Time Complexity
O(n² × m)
Space Complexity
O(n)
Tags
String DP Hash Set Memoization
Frequently Asked Questions
What is the optimal time and space complexity for Word Break?
The optimal solution for Word Break achieves O(n² × m) runtime complexity and requires O(n) auxiliary space. Time complexity is O(n^2 * k) where n is the length of s and k is the maximum word length (for substring hashing/copying). Space complexity is O(n + m) for the DP boolean array and the hash set.
How do I identify that Word Break requires the Dynamic Programming pattern?
In technical interviews, look for key problem signals: Can string be segmented using dictionary?. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Dynamic Programming strategy.
What critical edge cases must be handled in Word Break?
Essential edge cases to verify include: Single character matching dictionary word (e.g. s = "a", wordDict = ["a"]); No segmentation possible (e.g. s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]); Overlapping prefixes (e.g. s = "cars", wordDict = ["car", "ca", "rs"]); String where dictionary words must be reused multiple times (e.g. s = "applepenapple"). Always walk through these scenarios with your interviewer before coding.
Which tech companies frequently ask Word Break?
Word Break is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google, Facebook, Bloomberg.