139. Word Break
mediumAsked at TwilioWord Break is Twilio's DP-versus-recursion-with-memo probe: given a string s and a dictionary, determine if s can be segmented into a sequence of dictionary words. The grading rubric weighs whether you avoid exponential blowup with memoization or bottom-up DP, and choose a Set lookup for the dictionary.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Twilio loops.
- Glassdoor (2026-Q1)— Reported in Twilio backend SWE on-site rounds as the 'DP-or-memo' question.
- LeetCode Discuss (2025-12)— Recurring in Twilio platform-team interview reports.
Problem
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.
Constraints
1 <= s.length <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]trueExplanation: Return true because 'leetcode' can be segmented as 'leet code'.
Example 2
s = "applepenapple", wordDict = ["apple","pen"]trueExplanation: Return true. Note words may be reused.
Example 3
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falseApproaches
1. Plain recursion (rejected — exponential)
For each prefix that's a dictionary word, recurse on the suffix.
- Time
- O(2^n)
- Space
- O(n)
function wordBreakBrute(s, wordDict) {
const dict = new Set(wordDict);
const solve = (start) => {
if (start === s.length) return true;
for (let end = start + 1; end <= s.length; end++) {
if (dict.has(s.slice(start, end)) && solve(end)) return true;
}
return false;
};
return solve(0);
}Tradeoff: Correct but blows up on inputs like 'aaaaaaaaaab' with dict [a, aa, aaa, ...] — the same suffix gets recomputed exponentially many times. Twilio interviewers want you to name this then show memoization.
2. Bottom-up DP on prefix endings (optimal)
dp[i] = true iff s[0..i] is segmentable. dp[i] is true when some j < i has dp[j] true and s[j..i] is a dictionary word.
- Time
- O(n^2)
- Space
- O(n)
function wordBreak(s, wordDict) {
const dict = 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] && dict.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}Tradeoff: O(n^2) time at O(n) space. The Set lookup makes dict.has() O(L) where L is the average word length, but L is bounded by 20 per the constraints so it's effectively constant. Bottom-up is preferred over memoized recursion for stack-safety and clarity.
Twilio-specific tips
Twilio reviewers grade two things on Word Break: (1) you recognize the exponential blowup of plain recursion and propose memoization or DP without prompting, (2) you use a Set for the dictionary instead of Array.includes (which is O(L * |wordDict|) per lookup). The 'break' inside the inner loop is a clarity signal — confirms you understand that one valid split is enough.
Common mistakes
- Using Array.includes for dictionary lookup — turns each iteration into O(|wordDict|) and bloats the runtime by ~1000x.
- Forgetting the base case dp[0] = true (the empty prefix is trivially segmentable).
- Returning prematurely on the first dictionary-word match without continuing the recurrence — the FIRST word doesn't have to be the optimal split.
Follow-up questions
An interviewer at Twilio may pivot to one of these next:
- What if you needed to return all valid segmentations, not just whether one exists? (LC 140 — DP + backtracking to reconstruct.)
- What's the optimal-substring-length pruning? (Skip s[j..i] checks where (i - j) > max wordDict length.)
- How would you adapt to streaming input where s arrives one character at a time? (Same DP, you just extend dp by one cell per character.)
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is the bottom-up DP preferred over top-down memoization?
Both have the same asymptotic complexity. Bottom-up is preferred in interviews because it has no recursion stack (so it doesn't blow up on n = 300 in environments with low stack limits) and it's easier to reason about the state transitions visually.
Why is the inner-loop break safe?
Because dp[i] is a boolean — once it's true, no further work changes the answer for position i. Subsequent splits at i don't help find segmentations to the right of i.
Free learning resources
Curated free links for this problem.