Skip to main content

139. Word Break

mediumAsked at HP

HP's natural-language processing tools for document scanning and search decompose recognized text sequences into valid dictionary words — essentially the Word Break problem. HP uses it to assess dynamic programming depth and the ability to recognize overlapping subproblems in string segmentation.

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

Source citations

Public interview reports confirming this problem appears in HP loops.

  • Glassdoor (2025-Q3)— HP SWE onsite feedback cites Word Break in rounds involving DP and string manipulation.
  • Blind (2025-09)— HP interview prep threads recommend Word Break as a representative DP-on-strings problem for technical rounds.

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 (boolean array)

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

Time
O(n² * m) where m = average word length for substring check
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 trivially breakable
  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²) positions, O(n) per substring comparison. Convert wordDict to a Set first for O(1) lookups. Clear state transition: 'can I reach position i from some earlier reachable position j via a valid word?'

HP-specific tips

HP interviewers want you to state the DP formulation before coding: 'dp[i] = can we break s[0..i-1]? Base case: dp[0] = true. Transition: dp[i] = OR over all j where dp[j] is true and s[j..i] is a dictionary word.' Converting wordDict to a Set upfront is a simple optimization that shows awareness of lookup cost. Expect a follow-up asking you to return the actual word segments.

Common mistakes

  • Not setting dp[0] = true — the empty prefix must be the seed; all segmentations build on it.
  • Using wordDict as an array for lookup — O(n) per lookup vs O(1) for a Set; always convert first.
  • Off-by-one in the slice indices — s.slice(j, i) gives characters at positions j through i-1 (inclusive), matching the half-open interval [j, i).
  • Not breaking early after finding dp[i] = true — minor optimization but shows attention to performance.

Follow-up questions

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

  • Return all possible sentences from the segmentation (LC 140 — Word Break II).
  • What if no reuse of dictionary words is allowed?
  • How would you handle very long strings where O(n²) becomes too slow — consider a trie-based approach.

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?

dp[0] represents the empty prefix — zero characters. An empty string can trivially be 'segmented' into zero words. This base case seeds all subsequent transitions.

What is the time complexity more precisely?

O(n²) position pairs × O(k) for each s.slice comparison where k is the word length. With s.length = 300 and max word length 20, in practice it's very fast.

Can BFS/DFS solve this?

Yes — treat each position as a node; an edge exists from j to i if s[j..i-1] is a dictionary word. BFS from 0 finds s.length if reachable. The DP is essentially a flattened BFS with memoization.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →