Skip to main content

70. Word Break

mediumAsked at Datadog

Given a string and a dictionary, determine if the string can be segmented into a sequence of dictionary words. Datadog uses this for the 1D DP segmentation pattern — same shape as their tokenizer for tag-pattern matching on hierarchical metric names.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog onsite DP segmentation question.

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

Examples

Example 1

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

Example 2

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

Example 3

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

Approaches

1. Brute-force recursion

Try every prefix; if in dict, recurse on suffix.

Time
O(2^n)
Space
O(n)
// Recurse without memo. Exponential.

Tradeoff: Exponential — Datadog will require memoization.

2. 1D DP (optimal)

dp[i] = s[0..i] is segmentable. dp[i] = true if exists j < i where dp[j] && s[j..i] in dict.

Time
O(n^2 * L)
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.substring(j, i))) {
        dp[i] = true;
        break;
      }
    }
  }
  return dp[s.length];
}

Tradeoff: O(n^2 * L) for substring hash. Datadog-canonical 1D DP.

Datadog-specific tips

Datadog will probe with: 'Now return ALL valid segmentations' (LC 140) — that's backtracking + memoization. The decision version (this problem) is just dp[n].

Common mistakes

  • Forgetting dp[0] = true — base case.
  • Iterating j > i instead of j < i — wrong direction.
  • Computing substring inside the hot loop without optimization — fine for n=300, breaks for larger.

Follow-up questions

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

  • Word Break II (LC 140) — return all segmentations.
  • Concatenated Words (LC 472) — find all words composed of others.
  • Datadog-style: tokenize a hierarchical metric tag against a vocabulary.

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 1D DP works?

Each dp[i] depends only on dp[j] for j < i. Forward sweep is enough.

Faster than O(n^2)?

With a Trie of wordDict, you can scan from each position in O(max_word_len), giving O(n * L). Helpful for long dictionaries.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →