139. Word Break
mediumAsked at Juniper NetworksDetermine 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 Sam K., 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 <= 3001 <= wordDict.length <= 10001 <= wordDict[i].length <= 20s and wordDict[i] consist of only lowercase English letters.All the strings of wordDict are unique.
Examples
Example 1
s = "leetcode", wordDict = ["leet","code"]trueExplanation: "leetcode" can be segmented as "leet code".
Example 2
s = "applepenapple", wordDict = ["apple","pen"]trueExplanation: "apple pen apple" — apple is reused.
Example 3
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]falseExplanation: 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.
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.