How do you approach Word Break?

Use dynamic programming where dp[i] means the substring s[0..i-1] can be segmented.

What is the time complexity of Word Break?

Time complexity: O(n^2 * m) where n is string length and m is max word length. Space complexity: O(n).

What are common mistakes on Word Break?

Iterating the dimensions in an order that reads a cell before it has been written. Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input. Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

gitGood.dev

← Back to problems

Word Break

MediumAlgorithms

Description

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.

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

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3

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

Output: false

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.

Word Break: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Use dynamic programming where dp[i] means the substring s[0..i-1] can be segmented.
For each position i, check all possible last words ending at i.
Use a Set for O(1) word lookups.

The optimal approach

Show the approach: Dynamic Programming

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

Time: O(n^2 * m) where n is string length and m is max word length
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.

← Back to problems

Word Break

MediumAlgorithms

Description

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

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word.

Example 3

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

Output: false

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.

Word Break: approach, complexity and pitfalls

A medium dynamic programming problem, graded against 7 test cases (4 of them hidden).

The pattern: Dynamic Programming

Overlapping subproblems solved once and reused - the pattern candidates fear most.

Reach for it when you see: "Number of ways", "minimum/maximum cost", or a recursion that recomputes the same state.

More Dynamic Programmingproblems →

If you are stuck

Show the 3-step hint ladder

Use dynamic programming where dp[i] means the substring s[0..i-1] can be segmented.
For each position i, check all possible last words ending at i.
Use a Set for O(1) word lookups.

The optimal approach

Show the approach: Dynamic Programming

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

Time: O(n^2 * m) where n is string length and m is max word length
Space: O(n)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.

Common Dynamic Programming mistakes

These apply to the pattern as a whole, not just this problem.

Iterating the dimensions in an order that reads a cell before it has been written.
Getting the base case wrong. It carries the whole recurrence, and the error stays invisible until a large input.
Rolling down to one dimension without reversing the inner loop, which lets a 0/1 item be taken twice.