Skip to main content

139. Word Break

medium

Decide whether a string can be segmented into a sequence of dictionary words. The standard DP-on-prefixes approach turns an exponential search into O(n^2).

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

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: Return true because "leetcode" can be segmented as "leet code".

Example 2

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

Example 3

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

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Brute force tries every prefix as a possible first word, recurses on the rest. Exponential without memo.

Hint 2

DP: dp[i] = true iff s[0..i-1] can be segmented. dp[0] = true.

Hint 3

Transition: for each i, scan j < i. If dp[j] is true AND s[j..i-1] is in the dictionary, set dp[i] = true.

Solution approach

Reveal approach

Bottom-up DP on prefixes. Convert wordDict to a hash set for O(1) lookup. Allocate dp[n+1] initialized to false; dp[0] = true (empty string is segmentable). For i = 1..n: for each j from 0 to i-1, if dp[j] is true AND s[j..i-1] is in the dictionary set, set dp[i] = true and break out of the inner loop. Return dp[n]. O(n^2) inner work, multiplied by the substring hash cost (averaged O(max-word-length)). Practical optimization: only consider j's where i - j <= max word length.

Complexity

Time
O(n^2 * L)
Space
O(n + W)

Related patterns

  • dynamic-programming
  • hash-set

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Meta
  • Microsoft
  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Word Break and Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →