Skip to main content

139. Word Break

mediumAsked at Atlassian

Word Break is an Atlassian-favorite dynamic programming problem. Given a string s and a dictionary, determine whether s can be segmented into a space-separated sequence of dictionary words. Atlassian uses it to test memoization intuition before harder string-DP follow-ups.

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

Source citations

Public interview reports confirming this problem appears in Atlassian loops.

  • Glassdoor (2026-Q1)— Atlassian onsite reports cite Word Break as a recurring string-DP problem at SWE-II and Senior loops.
  • Blind (2025-08)— Atlassian interview threads mention Word Break leading to Word Break II as a common 'is, then enumerate' progression.

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

Example 2

Input
s = "applepenapple", wordDict = ["apple","pen"]
Output
true

Explanation: Return true because 'applepenapple' = 'apple pen apple'.

Example 3

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

Approaches

1. Naive recursion (TLE)

For each prefix, if it's a word try to break the suffix recursively. Returns true if any split works.

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

Tradeoff: Times out on long strings — same subproblems explode. Useful only to motivate memoization.

2. Top-down memoization

Same recursion but cache the answer per start index. Each index is solved once.

Time
O(n^2 * k) where k is max word length
Space
O(n)
function wordBreakMemo(s, wordDict) {
  const set = new Set(wordDict);
  const memo = new Map();
  const helper = (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)) && helper(end)) {
        memo.set(start, true);
        return true;
      }
    }
    memo.set(start, false);
    return false;
  };
  return helper(0);
}

Tradeoff: Clear progression from brute. Most Atlassian interviewers accept this and move on; some push for the bottom-up version because it eliminates the recursion stack risk for very long inputs.

3. Bottom-up DP (optimal, idiomatic)

dp[i] = true if s[0..i] is breakable. dp[i] = OR over j < i of dp[j] AND wordDict contains s[j..i].

Time
O(n^2 * k)
Space
O(n)
function wordBreak(s, wordDict) {
  const set = new Set(wordDict);
  const dp = new Array(s.length + 1).fill(false);
  dp[0] = true;
  let maxLen = 0;
  for (const w of wordDict) if (w.length > maxLen) maxLen = w.length;
  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: The maxLen pruning is the optimization Atlassian interviewers explicitly call out — without it the inner loop is wasteful. Don't ship the unpruned version; mention the prune as you write it.

Atlassian-specific tips

Atlassian's coding rubric scores 'recognizes overlapping subproblems'. Walk through the recursive solution and EXPLICITLY POINT AT where you'd visit the same start index twice — that's how you earn the memoization point. Then show the bottom-up version with the maxLen prune. After you finish, expect 'now return ALL valid segmentations' (Word Break II) which forces backtracking with the memo as a viability gate.

Common mistakes

  • Forgetting dp[0] = true — the empty prefix is always breakable, and missing this makes the whole table false.
  • Iterating j from 0 to i for every i without the maxLen prune — burns most of the time budget on impossible word slices.
  • Using a list for wordDict and doing array.includes on every check — switch to Set for O(1) lookup.

Follow-up questions

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

  • Word Break II (LeetCode 140) — return EVERY valid segmentation as a list of strings; memo + backtrack.
  • Concatenated Words (LeetCode 472) — return all words in a list that are concatenations of OTHER words in the list.
  • What if the dictionary is too large to fit in memory? Use a trie and walk down it as you scan s.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Is the trie approach worth mentioning?

Only on the followup where the dictionary is huge. For LeetCode's constraints the Set+DP version is faster because hash lookup beats trie traversal by a constant factor. Save the trie answer for the 'massive dictionary' follow-up.

Why does Atlassian like Word Break?

Because it's a clean test for whether you can move from 'I see the recursive structure' to 'I see the overlapping subproblems' to 'I can write the bottom-up table'. Three rubric points in one problem.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →