Skip to main content

139. Word Break

mediumAsked at IBM

Word Break is IBM's DP-on-strings screener. The interviewer is grading whether you recognize the 'can-be-split' DP recurrence, whether you build the Set for O(1) word lookup, and whether you bound the inner loop by the maximum word length to avoid pathological inputs.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in IBM loops.

  • Glassdoor (2026-Q1)— IBM SWE-2 / SWE-3 recurring onsite problem (DP track).
  • LeetCode (2026-Q1)— Top-30 IBM-tagged problem (medium tier). Watson NLP team specifically cites.
  • GeeksforGeeks (2025-12)— Listed in IBM interview-experience archive with DP/memoization variants.

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: Note that you are allowed to reuse a dictionary word.

Example 3

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

Approaches

1. Naive recursion (no memo)

Try every prefix; if it's in the dict, recurse on the suffix.

Time
O(2^n)
Space
O(n) stack
function wordBreakNaive(s, wordDict) {
  const set = new Set(wordDict);
  const solve = (start) => {
    if (start === s.length) return true;
    for (let end = start + 1; end <= s.length; end++) {
      if (set.has(s.slice(start, end)) && solve(end)) return true;
    }
    return false;
  };
  return solve(0);
}

Tradeoff: Exponential. At n=300 this is impossibly slow — useful only to derive the memoized version. Always state the exponential cost out loud before adding the memo.

2. Top-down DP with memo

Same recursion, cache the can-segment result by start index.

Time
O(n^2 * m)
Space
O(n)
function wordBreakMemo(s, wordDict) {
  const set = new Set(wordDict);
  const memo = new Map();
  const solve = (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 (set.has(s.slice(start, end)) && solve(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  };
  return solve(0);
}

Tradeoff: Polynomial — the memo eliminates re-exploring subproblems. m is the average cost of the slice operation (effectively O(word length)). Mention this version as the bridge to the bottom-up tabulation.

3. Bottom-up DP (optimal)

dp[i] = true iff s[0..i] can be segmented. Transition: dp[i] = OR over j < i of (dp[j] AND s[j..i] in dict).

Time
O(n^2)
Space
O(n)
function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const maxLen = Math.max(...wordDict.map((w) => w.length));
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  for (let i = 1; i <= s.length; i++) {
    for (let j = Math.max(0, i - maxLen); j < i; j++) {
      if (dp[j] && set.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: Bottom-up version with the max-word-length bound on the inner loop. Without that bound, pathological inputs (s is all 'a's, dict is small) waste work checking impossible-length substrings. The break-on-success is another standard optimization.

IBM-specific tips

IBM Watson NLP and AI-research interviewers specifically grade the max-word-length optimization on this problem because it shows you've thought about pathological inputs. Saying 'I'll bound the inner loop by the longest word in the dictionary so we never check substrings that can't match' before coding is the rubric checkbox. Always state the DP recurrence — `dp[i] = true iff s[0..i] can be segmented` — in plain language before writing code.

Common mistakes

  • Forgetting dp[0] = true — the empty prefix is trivially segmentable; without this seed, dp[i] is false everywhere.
  • Looping the inner j from 0 to i without the max-word-length bound — quadratic with a large constant.
  • Using Array.includes on wordDict instead of building a Set — turns the dict lookup into O(m) per check.
  • Returning dp[s.length - 1] instead of dp[s.length] — off-by-one.
  • Slicing the string inside the inner loop without caching — creates O(n^3) substrings. Acceptable here but mention if asked.

Follow-up questions

An interviewer at IBM may pivot to one of these next:

  • Word Break II — return ALL possible segmentations (LeetCode 140) — DP + backtracking.
  • What if the dictionary is huge (10^6 words) and we want sub-linear lookup? (Trie.)
  • Concatenated Words — find words formed by concatenating other words (LeetCode 472).
  • What if word reuse were disallowed? (Track remaining-budget DP state.)

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 use a Set instead of the array?

Set.has() is O(1) average; Array.includes() is O(m). With up to 1000 words checked across an n^2 outer loop, the difference is 1000x. Always convert the dictionary to a Set as the first line of your function.

Why does the max-word-length bound matter?

It changes the inner loop from O(n) to O(maxLen). On strings of all 'a' with short words, this is the difference between 90,000 and 6,000 inner iterations. The asymptotic complexity is the same, but the constant factor is smaller and signals that you've considered real-world inputs.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →