Skip to main content

23. Word Break

mediumAsked at ServiceNow

Determine if a string can be segmented into words from a dictionary using dynamic programming. ServiceNow uses this to test DP problem decomposition — the same bottom-up memoization pattern powers their rule-engine tokenization for workflow trigger parsing.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • LeetCode Discuss (2025)— Reported as a ServiceNow SDE-II phone screen DP question.
  • Blind (2026)— Listed in ServiceNow interview prep threads alongside Trie and LRU Cache.

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 in wordDict are unique.

Examples

Example 1

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

Explanation: 'leetcode' can be split as 'leet code'.

Example 2

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

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

Approaches

1. Recursive backtracking without memoization

Try every split point; recurse on the suffix if the prefix is in the dictionary.

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

Tradeoff: Exponential without memoization — recomputes the same suffix subproblems repeatedly. Fails on inputs like 'aaaa...b' where no valid segmentation exists.

2. Bottom-up DP with boolean array

Build dp[0..n] where dp[i] = true means s[0..i-1] can be segmented. dp[0] = true (empty prefix). For each position i, check all j < i: if dp[j] is true and s[j..i] is in the dictionary, set dp[i] = true.

Time
O(n^2 * L) where L = avg word length for substring
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; // found a valid segmentation to position i
      }
    }
  }
  return dp[n];
}

Tradeoff: O(n^2) iterations, each with a substring operation. Using a trie for the word set can reduce the inner work, but for n=300 the naive version passes. The break statement is an important optimization.

ServiceNow-specific tips

ServiceNow interviewers look for candidates who explicitly state the dp[0] = true base case and why it's correct — 'an empty prefix can always be trivially segmented.' They also reward the break optimization inside the inner loop. Bonus signal: connect this to ServiceNow's flow-designer rule parser, where valid trigger expressions must be segmentable into known condition tokens.

Common mistakes

  • Forgetting dp[0] = true — causes the DP to never find any valid segmentation because no starting position is true.
  • Using dp[i] to represent s[0..i] (inclusive) instead of s[0..i-1] — causes off-by-one confusion in the slice indices.
  • Not breaking out of the inner loop once dp[i] is set — wastes time and can produce subtle bugs if the loop mutates shared state.

Follow-up questions

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

  • Word Break II: return all possible sentences (LC 140) — requires memoized recursion returning lists.
  • Add a max-word-length optimization: inner j only needs to go back max_word_len steps.
  • Word Break with trie: preload wordDict into a trie to traverse both s and the trie simultaneously.

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 does dp[0] = true make sense?

dp[0] represents the empty string prefix, which requires zero words and is trivially valid. Without this anchor, dp[i] for any i would never become true because there would be no valid 'previous position' to build from.

What is the time complexity if words are very long?

The s.slice(j, i) operation is O(i-j). Total work is O(sum over all (i,j) of substring length) = O(n^3) in the worst case. For n=300 this is 27 million operations — acceptable. A trie reduces this but adds implementation complexity.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →