Skip to main content

139. Word Break

mediumAsked at Akamai

Determine if a string can be segmented into words from a dictionary. Akamai frames this as rule-matching in edge logic — determining whether a URL path can be decomposed into a sequence of known routing tokens is the same dynamic programming problem applied to real-time request handling.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2025-11)— Akamai SWE onsite reports list Word Break as a dynamic programming question in algorithm rounds.
  • Blind (2025-09)— Akamai threads note DP on strings is a recurring category, with Word Break as a representative example.

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. The same word in the dictionary may be reused multiple times.

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: 'leetcode' = 'leet' + 'code'.

Example 2

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

Explanation: 'apple' + 'pen' + 'apple'. Reuse is allowed.

Example 3

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

Explanation: No valid segmentation covers the full string.

Approaches

1. DP bottom-up

dp[i] = true if s[0..i-1] can be segmented. For each position i, check all previous positions j where dp[j] is true and s[j..i-1] is a dictionary word.

Time
O(n² * m)
Space
O(n)
function wordBreak(s, wordDict) {
  const wordSet = new Set(wordDict);
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true; // empty prefix is always valid
  for (let i = 1; i <= n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && wordSet.has(s.slice(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[n];
}

Tradeoff: O(n² * m) where m is avg word length for substring operations. The Set lookup is O(m) per check. For n=300, this is well within limits. The break on dp[i]=true prunes unnecessary checks.

2. BFS (word-start positions as queue)

Use BFS from position 0. For each position in the queue, try extending by every dictionary word. If a word matches starting at the current position, add the end position to the queue. Reach position n = success.

Time
O(n * L)
Space
O(n)
function wordBreak(s, wordDict) {
  const n = s.length;
  const visited = new Set();
  const queue = [0];
  while (queue.length) {
    const start = queue.shift();
    if (visited.has(start)) continue;
    visited.add(start);
    for (const word of wordDict) {
      const end = start + word.length;
      if (end <= n && s.slice(start, end) === word) {
        if (end === n) return true;
        queue.push(end);
      }
    }
  }
  return false;
}

Tradeoff: Equivalent complexity, useful if the interviewer asks for a BFS framing. The visited set is critical to avoid reprocessing the same start positions.

Akamai-specific tips

Akamai interviewers often ask for the DP recurrence before the code: 'dp[i] = true if there exists some j < i such that dp[j] = true and s[j..i-1] is in the dictionary.' State the base case (dp[0] = true — the empty prefix is always valid) and the transition before writing a single line. This structured approach consistently impresses Akamai interview panels.

Common mistakes

  • Using wordDict.includes() inside the inner loop — O(m) per call where m is dictionary size. Convert to Set first for O(1) lookup.
  • Forgetting dp[0] = true — without the base case, dp[i] for every word starting at 0 would be false.
  • Not breaking inner loop after dp[i] = true — leads to redundant work but not incorrectness; still worth mentioning.

Follow-up questions

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

  • Word Break II (LC 140) — return all valid segmentations, not just true/false.
  • How does the complexity change if words can be up to length 300?
  • How would you handle this if the dictionary is too large to fit in memory?

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 initialize dp[0] = true?

dp[0] represents the empty prefix — no characters consumed. It is always a valid segmentation point (vacuously true). Without it, no word starting at position 0 could be accepted.

Is memoized recursion equivalent?

Yes — top-down with a memo array achieves the same O(n²*m) complexity. Bottom-up DP avoids the recursion call stack overhead and is easier to reason about for large n.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →