Word Break

▶

Steps

setup

Initialize word set and word lengths

Create a set of dictionary words and a set of their lengths for quick membership and length checks.

💡 Precomputing these sets allows efficient substring checks and limits substring lengths to consider.

Line:

word_set = set(wordDict)
word_lengths = set(len(word) for word in wordDict)

💡 We only need to check substrings of lengths present in the dictionary, reducing unnecessary checks.

setup

Initialize dp array with dp[0] = True

Create a dp array of length n+1 initialized to False, then set dp[0] = True to represent empty substring.

💡 dp[0] = True means an empty string can always be segmented (base case).

Line:

n = len(s)
dp = [False] * (n + 1)
dp[0] = True

💡 This base case allows building solutions for longer prefixes.

fill_cells

Start filling dp for i=1

Check substrings ending at index 1 (prefix 'l') for dictionary matches of allowed lengths.

💡 We try to find if s[0:1] can be segmented by checking substrings of lengths in word_lengths.

Line:

for i in range(1, n + 1):
    for length in word_lengths:

💡 We iterate over substring lengths to check possible segmentations at each position.

compare

Check length=4 for i=1 (too long, skip)

Check if length 4 substring ending at i=1 is valid; since 4 > 1, skip this length.

💡 We only consider substring lengths that fit within the current prefix length i.

Line:

if length <= i:

💡 Lengths longer than current prefix cannot form valid substrings here.

compare

Check length=5 for i=1 (too long, skip)

Check if length 5 substring ending at i=1 is valid; since 5 > 1, skip this length.

💡 Again, substring length must not exceed current prefix length.

Line:

if length <= i:

💡 No valid substring of length 5 can end at position 1.

fill_cells

Finish dp[1] with no matches

No substring matched dictionary words for dp[1], so dp[1] remains False.

💡 If no valid segmentation found, dp[i] stays False.

Line:

dp[i] = True if condition else dp[i]

💡 dp[1] = False means s[0:1] ('l') cannot be segmented.

fill_cells

Start filling dp for i=4

Check substrings ending at i=4 (prefix 'leet') for dictionary matches of lengths 4 and 5.

💡 We focus on dp[4], checking if s[0:4] can be segmented.

Line:

for i in range(1, n + 1):
    for length in word_lengths:

💡 We test substrings of length 4 and 5 ending at position 4.

compare

Check length=4 for i=4: substring 'leet' in dictionary and dp[0] is True

Since dp[0] is True and substring s[0:4] = 'leet' is in word_set, set dp[4] = True.

💡 This means the prefix 'leet' can be segmented as a dictionary word.

Line:

if length <= i and dp[i - length] and s[i - length:i] in word_set:
    dp[i] = True
    break

💡 dp[4] = True means s[0:4] can be segmented successfully.

fill_cells

Start filling dp for i=8

Check substrings ending at i=8 (full string 'leetcode') for dictionary matches of lengths 4 and 5.

💡 We want to determine if the entire string can be segmented.

Line:

for i in range(1, n + 1):
    for length in word_lengths:

💡 We test substrings of length 4 and 5 ending at position 8.

compare

Check length=4 for i=8: substring 'code' in dictionary and dp[4] is True

Since dp[4] is True and substring s[4:8] = 'code' is in word_set, set dp[8] = True.

💡 This means the suffix 'code' can be segmented and the prefix up to 4 is segmentable.

Line:

if length <= i and dp[i - length] and s[i - length:i] in word_set:
    dp[i] = True
    break

💡 dp[8] = True means the entire string can be segmented.

reconstruct

Return final answer dp[n]

Return dp[8], which is True, indicating the string can be segmented.

💡 The final dp value tells if the entire string is segmentable.

Line:

return dp[n]

💡 The algorithm confirms the string 'leetcode' can be segmented into dictionary words.

def wordBreak(s, wordDict):
    word_set = set(wordDict)  # STEP 1
    word_lengths = set(len(word) for word in wordDict)  # STEP 1
    n = len(s)  # STEP 2
    dp = [False] * (n + 1)  # STEP 2
    dp[0] = True  # STEP 2
    for i in range(1, n + 1):  # STEP 3,7,9
        for length in word_lengths:  # STEP 3,7,9
            if length <= i and dp[i - length] and s[i - length:i] in word_set:  # STEP 4,5,8,10
                dp[i] = True  # STEP 8,10
                break
    return dp[n]  # STEP 11

if __name__ == '__main__':
    s = "leetcode"
    wordDict = ["leet", "code"]
    print(wordBreak(s, wordDict))

📊

Word Break - Watch the Algorithm Execute, Step by Step

Watching each dp cell update reveals how the algorithm builds solutions from smaller substrings, making the logic clear without needing to read code.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Visualization unavailable for this step.

Key Takeaways

✓ The dp array represents whether prefixes of the string can be segmented into dictionary words.

This is hard to see from code alone because the dp array is a simple boolean list without explicit explanation.

✓ Only substrings of lengths present in the dictionary are checked, optimizing the algorithm.

This reduces unnecessary substring checks and clarifies the dependency structure visually.

✓ When dp[i] is set to True, it means a valid segmentation ending at i was found, allowing early break from inner loop.

Seeing this decision in the trace helps understand how the algorithm avoids redundant checks.

Practice

1. What is the time complexity of the optimal bottom-up dynamic programming solution for the minimum cost climbing stairs problem, and why?

medium

A. O(n) because each step computes cost using only two previous states

B. O(n²) because each step depends on all previous steps

C. O(2^n) due to exponential recursion calls

D. O(n log n) because of sorting costs before processing

Solution

1. Step 1: Analyze loop structure

   The bottom-up DP iterates once through the cost array of length n.

2. Step 2: Check dependencies per iteration

   Each iteration computes current cost using only two previous values, constant time per iteration.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Single pass with O(1) work per step -> O(n) total [OK]

Hint: DP uses constant work per step, linear total time [OK]

Common Mistakes:

• Assuming quadratic due to nested loops
• Confusing recursion with DP iteration
• Thinking sorting is involved

2. Consider the following buggy code for minimum cost climbing stairs. Which line contains the subtle bug that causes incorrect results on some inputs?

medium

A. Line 4: Loop range starting at 2

B. Line 7: Returning prev1 instead of min(prev1, prev2)

C. Line 6: Updating prev2 and prev1

D. Line 3: Initialization of prev2 and prev1

Solution

1. Step 1: Understand final return logic

   The top can be reached from either last step or second last step, so minimum of prev1 and prev2 must be returned.

2. Step 2: Identify incorrect return

   Returning only prev1 ignores the possibility that prev2 might be cheaper, causing wrong results.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Return min(prev1, prev2) to cover both possible last steps [OK]

Hint: Return min of last two costs, not just last [OK]

Common Mistakes:

• Forgetting min at return
• Misinitializing base cases
• Incorrect loop boundaries

3. Suppose the problem is modified so that you can reuse the same stock multiple times within a single transaction (i.e., buy and sell multiple times without waiting). Which modification to the DP approach correctly handles this variant?

hard

A. Modify the DP to allow buying again without decrementing transactions_left when holding a stock

B. Increase k to a very large number and use the unlimited transactions solution shortcut

C. Use the same DP but skip updating buy states to avoid multiple buys

D. Use a greedy approach to sum all positive price differences without DP

Solution

1. Step 1: Understand the reuse variant

   Reusing stock within a transaction means multiple buys/sells without reducing transaction count on buys.

2. Step 2: Modify DP state transitions

   Allow buy state updates without decrementing transactions_left, so holding state can be refreshed multiple times per transaction.

3. Step 3: Why other options fail

   Unlimited transactions shortcut ignores transaction limit; skipping buy updates breaks profit calculation; greedy fails with transaction constraints.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct DP modification respects transaction count and allows multiple buys per transaction [OK]

Hint: Allow buy updates without reducing transactions_left [OK]

Common Mistakes:

• Using unlimited transactions shortcut incorrectly
• Skipping buy updates breaks DP correctness

4. Suppose the House Robber problem is modified so you can rob the same house multiple times (unlimited reuse). Which of the following changes to the algorithm correctly computes the maximum amount you can rob?

hard

A. Use the original DP but allow robbing adjacent houses since reuse is allowed

B. Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement

C. Use a new DP where dp[i] = max(dp[i-1], dp[i-2] + nums[i]) but allow revisiting dp[i] multiple times

D. Modify DP to consider robbing the current house plus the best solution including the current house again (i.e., dp[i] = max(dp[i-1], dp[i] + nums[i]))

Solution

1. Step 1: Understand problem change

   Allowing unlimited reuse means we can rob the same house multiple times, similar to unbounded knapsack.

2. Step 2: Identify correct DP formulation

   Unbounded knapsack style DP updates dp[i] considering dp[i - 1] + nums[i] repeatedly until stable.

3. Step 3: Evaluate options

   Use unbounded knapsack approach: dp[i] = max(dp[i], dp[i - 1] + nums[i]) iterating until no improvement correctly describes iterative updates until no improvement, matching unbounded knapsack logic.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Original adjacency constraints no longer apply; unbounded knapsack DP fits [OK]

Hint: Reuse means unbounded knapsack, not original adjacency DP [OK]

Common Mistakes:

• Trying to reuse original adjacency DP
• Ignoring repeated state updates

5. Suppose the problem changes so you can climb 1, 2, or 3 steps at a time. Which modification to the bottom-up DP approach correctly computes the minimum cost to reach the top?

hard

A. Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop

B. Keep the original code but run the loop until n+1 to cover extra steps

C. Use a greedy approach picking the cheapest next step among 1, 2, or 3 steps

D. Change the recurrence to curr = cost[i] + min(prev1, prev2, prev3) and track three previous states

Solution

1. Step 1: Understand new step options

   With 1, 2, or 3 steps allowed, the cost to reach step i depends on the minimum cost to reach steps i-1, i-2, and i-3.

2. Step 2: Modify DP recurrence and state tracking

   Track three previous states (prev1, prev2, prev3) and compute curr = cost[i] + min(prev1, prev2, prev3) to cover all possibilities.

3. Step 3: Reject incorrect options

   Change the recurrence to curr = cost[i] + min(prev1, prev2) and keep the same loop ignores the third previous step, greedy fails to guarantee global minimum, and extending loop without updating recurrence is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DP recurrence must consider all allowed step sizes [OK]

Hint: Include all allowed previous steps in min calculation [OK]

Common Mistakes:

• Ignoring new step size in recurrence
• Using greedy instead of DP
• Extending loop without recurrence update