Skip to main content

139. Word Break

mediumAsked at Twilio

Word 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 Alex Chen, 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 <= 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.

Examples

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. Note words may be reused.

Example 3

Input
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output
false

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Word Break and other Twilio interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →