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 Sam K., 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

More Dynamic Programming practice problems

See all Dynamic Programming problems →