Skip to main content

139. Word Break

mediumAsked at Juniper Networks

Determine whether a string can be segmented into words from a dictionary using dynamic programming. Juniper asks this in software roles because tokenizing CLI command strings and configuration keywords against a known vocabulary — exactly the problem Junos CLI parsing faces — maps directly to this DP structure.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2025-Q3)— Reported in Juniper SWE onsite reports as a DP string problem appearing in software and platform interviews.
  • Blind (2025-09)— Listed in Juniper interview prep threads as a medium DP problem with clear CLI parsing analogies.

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: "leetcode" can be segmented as "leet code".

Example 2

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

Explanation: "apple pen apple" — apple is reused.

Example 3

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

Explanation: No valid segmentation exists.

Approaches

1. Bottom-up DP

dp[i] = true if s[0..i-1] can be segmented. For each position i, check all substrings s[j..i-1]: if dp[j] is true and s[j..i-1] is in the word set, then dp[i] = true.

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

Tradeoff: O(n²) time ignoring string hashing, O(n) space. The Set lookup makes the word check O(m) but is effectively O(1) for typical dictionary sizes. This is the canonical DP solution.

Juniper Networks-specific tips

State the DP invariant explicitly before coding: 'dp[i] is true if the prefix s[0..i-1] can be segmented using dictionary words.' This kind of precise subproblem definition signals that you think in DP idioms. Juniper interviewers will ask about the time complexity — distinguish the O(n²) loop cost from the Set lookup cost. Also mention converting wordDict to a Set upfront (O(1) lookup vs O(len) linear scan per word).

Common mistakes

  • Not seeding dp[0] = true — the empty prefix is always valid, and it seeds the DP correctly.
  • Not converting wordDict to a Set — O(k) lookup per check instead of O(1).
  • Using s.includes() or indexOf() instead of the dp array — these O(n²) scans don't memoize subproblem results.
  • Off-by-one in slice indices — s.slice(j, i) extracts characters at positions j through i-1.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Word Break II (LC 140) — return all valid segmentations, not just whether one exists.
  • How would you extend this to handle fuzzy matching (dictionary words that are close but not exact)?
  • How does this relate to CYK parsing in formal language theory?

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?

It represents the empty string, which is trivially segmentable. Without it, no transition can be seeded and all dp values stay false.

What is the time complexity?

O(n²) for the double loop, with each slice and Set lookup taking O(m) where m is the word length. In practice, m is small (bounded by 20), making it effectively O(n²).

Can the same word be reused?

Yes — the problem explicitly allows it. The DP handles reuse naturally because dp[j] can be set from any prior position, and the same dictionary word can be matched at multiple positions.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →