Fetching algorithms...

Word Break Problem Visualizer & Solution | Rulcode

87. Word Break Problem

Medium

Topics

Companies

Hint

Understand Before Coding

Loading visualization...

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]

Output: true

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]

Output: true

Constraints:

Time Complexity

O(n²)

Space Complexity

O(n)

Loading problem details...

rulcode

87. Word Break Problem

Medium

Topics

Companies

Hint

Understand Before Coding

Step 1 / 73

Speed: 1.0x

Dictionary: ["leet", "code"]

Input String (s = "leetcode")

DP Array (Prefix of length i is segmentable)

i = 0

i = 1

i = 2

i = 3

i = 4

i = 5

i = 6

i = 7

i = 8

Why this works

`dp[i]` is true if the prefix of length `i` (`s[0...i-1]`) can be segmented.

To check this, we look at all split points `j` from 0 to `i - 1`. If `dp[j]` is true (prefix `s[0...j-1]` is valid) and the suffix `s[j...i-1]` is in the dictionary, then `dp[i]` is set to true.

If we find any valid segmentation, we break early to optimize.

Step Explanation

Initialize the word set for fast lookups and get the input string length.

Variables

s"leetcode"

wordDict["leet", "code"]

Loading visualization...

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

Example 1:

Input: s = "leetcode", wordDict = ["leet","code"]

Output: true

Example 2:

Input: s = "applepenapple", wordDict = ["apple","pen"]

Output: true

Constraints:

Time Complexity

O(n²)

Space Complexity

O(n)

Step 1 / 73

Speed: 1.0x

Dictionary: ["leet", "code"]

Input String (s = "leetcode")

DP Array (Prefix of length i is segmentable)

i = 0

i = 1

i = 2

i = 3

i = 4

i = 5

i = 6

i = 7

i = 8

Why this works

`dp[i]` is true if the prefix of length `i` (`s[0...i-1]`) can be segmented.

To check this, we look at all split points `j` from 0 to `i - 1`. If `dp[j]` is true (prefix `s[0...j-1]` is valid) and the suffix `s[j...i-1]` is in the dictionary, then `dp[i]` is set to true.

If we find any valid segmentation, we break early to optimize.

Step Explanation

Initialize the word set for fast lookups and get the input string length.

Variables

s"leetcode"

wordDict["leet", "code"]

87. Word Break Problem

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

87. Word Break Problem

Understand Before Coding

Input String (s = "leetcode")

DP Array (Prefix of length i is segmentable)

Why this works

Step Explanation

Variables

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

Input String (s = "leetcode")

DP Array (Prefix of length i is segmentable)

Why this works

Step Explanation

Variables