Skip to main content

20. Word Break

mediumAsked at DigitalOcean

Determine if a string can be segmented using a dictionary — a DP problem that mirrors token parsing in config-automation pipelines.

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

Problem

Given a string s and a dictionary wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. The same word may be reused multiple times.

Constraints

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20

Examples

Example 1

Input
s = 'leetcode', wordDict = ['leet','code']
Output
true

Example 2

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

Approaches

1. Recursive backtracking (no memo)

Try every split point; exponential without memoization due to overlapping subproblems.

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

Tradeoff:

2. Bottom-up DP

dp[i] is true if s[0..i-1] can be segmented. For each position j, check if dp[j] is true and s[j..i] is in the dictionary. O(n^2) with Set lookup.

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

Tradeoff:

DigitalOcean-specific tips

DigitalOcean infrastructure automation (e.g., Terraform provider name parsing) uses this exact segmentation pattern — mentioning the real-world analogy earns bonus points.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →