Word Break II (All Sentences)

▶

Steps

setup

Initialize dp array with empty lists and base case

Create a dp array of length n+1 where each element is an empty list. Set dp[n] to contain an empty string as the base case, representing an empty suffix.

💡 This base case allows the algorithm to build sentences backward by appending words to sentences starting at the end.

Line:

dp = [[] for _ in range(n + 1)]
dp[n] = [""]

💡 The base case dp[n] = [''] is essential to start building sentences from the end of the string.

fill_row

Start filling dp at position i=9 (last character 'g')

Set i to 9, the last index of s. We will check dictionary words that match s starting at i to build dp[9].

💡 Filling dp from the end ensures we have sentences for suffixes to append to when building earlier positions.

Line:

for i in range(n - 1, -1, -1):
    sentences = []

💡 We begin checking matches at the last character to build sentences starting there.

compare

Check word 'dog' at position i=9

Check if 'dog' matches s starting at index 9. It does not because s[9:] = 'g' only.

💡 Only words that fit fully starting at i can be used to build sentences here.

Line:

if s.startswith(word, i):

💡 Words longer than remaining substring cannot match.

fill_cells

Finish dp[9] with no sentences

No dictionary words matched at position 9, so dp[9] remains empty.

💡 Empty dp[i] means no valid sentence can start at position i.

Line:

dp[i] = sentences

💡 Positions with no matches yield empty sentence lists.

fill_row

Fill dp[8] checking dictionary words

Set i=8 and check each dictionary word if it matches s starting at 8 to build dp[8].

💡 We try to find words starting at position 8 to build sentences from dp[8].

Line:

for word in word_set:
    if s.startswith(word, i):

💡 Matching words at position 8 will be appended to sentences from dp[i+len(word)].

compare

Check word 'dog' at i=8, match found

'dog' matches s starting at 8 ('dog'). Append 'dog' + sentences from dp[11] (dp[11] out of range, so dp[11] empty).

💡 Matching word allows building sentences by appending to dp at position after the word.

Line:

if s.startswith(word, i):
    for sentence in dp[i + len(word)]:
        sentences.append(word + (" " + sentence if sentence else ""))

💡 dp[8] gains ['dog'] because dp[11] is empty (index out of range, treated as empty). Actually dp length is 11, so dp[11] invalid, so no sentences appended.

fill_cells

Finish dp[8] with sentences ['dog']

Set dp[8] to ['dog'] as the only valid sentence starting at index 8.

💡 dp[8] now holds all sentences starting at position 8.

Line:

dp[i] = sentences

💡 dp[8] contains one valid sentence 'dog'.

fill_row

Fill dp[7] checking dictionary words

Set i=7 and check dictionary words that match s starting at 7 to build dp[7].

💡 We look for words starting at position 7 to build sentences from dp[7].

Line:

for word in word_set:
    if s.startswith(word, i):

💡 Matching words at position 7 will be appended to sentences from dp[i+len(word)].

compare

Check word 'and' at i=7, no match

'and' does not match s starting at 7 ('og').

💡 Only exact matches at position i are considered.

Line:

if s.startswith(word, i):

💡 Words not matching at i are ignored.

compare

Check word 'sand' at i=7, no match

'sand' does not match s starting at 7 ('og').

💡 Words longer than remaining substring or mismatched are skipped.

Line:

if s.startswith(word, i):

💡 No sentences added for 'sand' at dp[7].

fill_cells

Finish dp[7] with no sentences

No dictionary words matched at position 7, so dp[7] remains empty.

💡 Empty dp[7] means no valid sentence starts at index 7.

Line:

dp[i] = sentences

💡 dp[7] = [] indicates no valid suffix sentences from position 7.

fill_row

Fill dp[6] checking dictionary words

Set i=6 and check dictionary words that match s starting at 6 to build dp[6].

💡 We try to find words starting at position 6 to build sentences from dp[6].

Line:

for word in word_set:
    if s.startswith(word, i):

💡 Matching words at position 6 will be appended to sentences from dp[i+len(word)].

compare

Check word 'and' at i=6, match found

'and' matches s starting at 6 ('anddog'). Append 'and' + sentences from dp[9] (dp[9] is empty).

💡 Appending words to sentences from dp[i+len(word)] builds new sentences at dp[i].

Line:

if s.startswith(word, i):
    for sentence in dp[i + len(word)]:
        sentences.append(word + (" " + sentence if sentence else ""))

💡 No sentences added because dp[9] is empty, so 'and' cannot form a valid sentence here.

compare

Check word 'sand' at i=6, match found

'sand' matches s starting at 6 ('sanddog'). Append 'sand' + sentences from dp[10] (dp[10] = ['']).

💡 Appending 'sand' to sentences from dp[10] builds new sentences at dp[6].

Line:

if s.startswith(word, i):
    for sentence in dp[i + len(word)]:
        sentences.append(word + (" " + sentence if sentence else ""))

💡 dp[6] gains ['sand'] as a valid sentence suffix.

fill_cells

Finish dp[6] with sentences ['sand']

Set dp[6] to ['sand'] as the only valid sentence starting at index 6.

💡 dp[6] now holds all sentences starting at position 6.

Line:

dp[i] = sentences

💡 dp[6] contains one valid sentence 'sand'.

fill_row

Fill dp[3] checking dictionary words

Set i=3 and check dictionary words that match s starting at 3 to build dp[3].

💡 We try to find words starting at position 3 to build sentences from dp[3].

Line:

for word in word_set:
    if s.startswith(word, i):

💡 Matching words at position 3 will be appended to sentences from dp[i+len(word)].

compare

Check word 'and' at i=3, match found

'and' matches s starting at 3 ('anddog'). Append 'and' + sentences from dp[6] (dp[6] = ['sand']).

💡 Appending 'and' to sentences from dp[6] builds new sentences at dp[3].

Line:

if s.startswith(word, i):
    for sentence in dp[i + len(word)]:
        sentences.append(word + (" " + sentence if sentence else ""))

💡 dp[3] gains ['and sand'] as a valid sentence suffix.

compare

Check word 'sand' at i=3, no match

'sand' does not match s starting at 3 ('anddog').

💡 Only exact matches at position i are considered.

Line:

if s.startswith(word, i):

💡 No sentences added for 'sand' at dp[3].

fill_cells

Finish dp[3] with sentences ['and sand']

Set dp[3] to ['and sand'] as the only valid sentence starting at index 3.

💡 dp[3] now holds all sentences starting at position 3.

Line:

dp[i] = sentences

💡 dp[3] contains one valid sentence 'and sand'.

fill_row

Fill dp[0] checking dictionary words and build final sentences

Set i=0 and check dictionary words that match s starting at 0. For each match, append the word plus sentences from dp[i+len(word)] to dp[0].

💡 This step builds all valid sentences for the entire string starting at index 0.

Line:

for word in word_set:
    if s.startswith(word, i):
        for sentence in dp[i + len(word)]:
            sentences.append(word + (" " + sentence if sentence else ""))
dp[i] = sentences

💡 dp[0] accumulates ['cat and sand', 'cats and dog'] as all valid sentences for the entire string.

from typing import List

def wordBreak(s: str, wordDict: List[str]) -> List[str]:
    word_set = set(wordDict)
    n = len(s)
    dp = [[] for _ in range(n + 1)]  # STEP 1: Initialize dp
    dp[n] = [""]  # STEP 1: Base case

    for i in range(n - 1, -1, -1):  # STEP 2: Iterate from end to start
        sentences = []  # STEP 2: Prepare sentences list
        for word in word_set:  # STEP 2: Check each word
            if s.startswith(word, i):  # STEP 3: Match word at i
                for sentence in dp[i + len(word)]:  # STEP 3: Append sentences from dp
                    sentences.append(word + (" " + sentence if sentence else ""))  # STEP 3
        dp[i] = sentences  # STEP 4: Save sentences at dp[i]

    return dp[0]  # STEP 7: Return all sentences for full string

📊

Word Break II (All Sentences) - Watch the Algorithm Execute, Step by Step

Watching the dp array fill step-by-step reveals how the algorithm builds all valid sentences incrementally, which is hard to grasp from code alone.

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10

Base case dp[n] = ['']

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10

Filling dp[9]

Item 4 - wt:3 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10

No match for 'dog'

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10

dp[9] = []

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8
i=9
i=10

Filling dp[8]

Item 4 - wt:3 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

Match 'dog'

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

dp[8] = ['dog']

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

Filling dp[7]

Item 2 - wt:3 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

No match 'and'

Item 3 - wt:4 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

No match 'sand'

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

dp[7] = []

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

Filling dp[6]

Item 2 - wt:3 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6
i=7
i=8	dog
i=9
i=10

No sentences from dp[9]

Item 3 - wt:4 val:0

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

Match 'sand'

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

dp[6] = ['sand']

Initializing dp array

i\w
i=0
i=1
i=2
i=3
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

Filling dp[3]

Item 2 - wt:3 val:0

i\w
i=0
i=1
i=2
i=3	and sand
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

Match 'and'

Item 3 - wt:4 val:0

i\w
i=0
i=1
i=2
i=3	and sand
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

No match 'sand'

Initializing dp array

i\w
i=0
i=1
i=2
i=3	and sand
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

dp[3] = ['and sand']

Initializing dp array

i\w	0	1
i=0	cat and sand	cats and dog
i=1
i=2
i=3	and sand
i=4
i=5
i=6	sand
i=7
i=8	dog
i=9
i=10

Final dp[0]

Key Takeaways

✓ The dp array stores all possible sentences starting at each index, built from the end backward.

This insight is hard to see from code alone because the dp array holds lists of strings, not just counts or booleans.

✓ Each dp[i] depends on dp[i + len(word)] for matching dictionary words, showing a backward dependency chain.

Visualizing this dependency clarifies why the algorithm fills dp from the end to the start.

✓ When multiple dictionary words match at the same position, dp[i] accumulates sentences from all branches, enabling multiple valid segmentations.

Seeing the branching in dp[i] helps understand how all valid sentences are collected.

Practice

1. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the edit distance problem, where m and n are the lengths of the two input strings?

medium

A. O(m + n)

B. O(m * n)

C. O(m * n * min(m, n))

D. O(m * n * log n)

Solution

1. Step 1: Identify nested loops over both strings

   The algorithm has two nested loops: outer over m and inner over n.

2. Step 2: Calculate total operations

   Each cell dp[j] is updated once per iteration, so total operations are proportional to m * n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Double loop over m and n -> O(m*n) [OK]

Hint: Nested loops over both strings imply O(m*n) time [OK]

Common Mistakes:

• Confusing with linear O(m+n)
• Adding extra factor min(m,n) incorrectly
• Assuming logarithmic factor

2. The following code attempts to implement the space-optimized DP for the interleaving string problem. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 12: inner loop iterating forward instead of backward

B. Line 10: dp[0] update before inner loop

C. Line 7: dp initialization with False values

D. Line 5: length check of s3 against s1 and s2

Solution

1. Step 1: Understand dp update order

   The dp array must be updated from right to left (descending j) to avoid overwriting dp[j-1] before it is used.

2. Step 2: Identify bug

   The inner loop iterates forward (j from 1 to n), which corrupts dp states and leads to incorrect results.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backward iteration preserves previous row info; forward breaks correctness [OK]

Hint: Space-optimized DP requires backward inner loop update [OK]

Common Mistakes:

• Updating dp forward overwrites needed states
• Forgetting length check causes unnecessary computation

3. The following code attempts to implement the space-optimized DP for longest common substring. Identify the line containing the subtle bug that causes incorrect results on some inputs.

def longest_common_substring_space_optimized_buggy(s1, s2):
    n, m = len(s1), len(s2)
    dp = [0] * (m + 1)
    max_len = 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):  # Note: iterating forward
            if s1[i - 1] == s2[j - 1]:
                dp[j] = dp[j - 1] + 1
                if dp[j] > max_len:
                    max_len = dp[j]
            else:
                dp[j] = 0
    return max_len

medium

A. Line with 'dp[j] = dp[j - 1] + 1' updating dp

B. Line with 'dp = [0] * (m + 1)' initializing dp array

C. Line with 'if dp[j] > max_len:' updating max_len

D. Line with 'for j in range(1, m + 1):' iterating forward

Solution

1. Step 1: Understand dp array update dependency

   dp[j] depends on dp[j-1] from previous iteration of inner loop, so iterating forward overwrites dp[j-1] before use.

2. Step 2: Identify iteration order bug

   Iterating j forward causes dp[j-1] to be updated before dp[j], corrupting the chain of matching lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Changing inner loop to iterate backward fixes the bug [OK]

Hint: DP update depends on previous dp[j-1], so iterate backward [OK]

Common Mistakes:

• Updating dp forward overwrites needed values
• Incorrect max_len update timing
• Wrong dp initialization size

4. Examine the following buggy code snippet for wildcard matching using space-optimized DP. Which line contains the subtle bug that causes incorrect results on empty strings or patterns?

medium

A. Line 14: curr[j] = curr[j - 1] or prev[j]

B. Line 10: curr = [False] * (n + 1) initialization

C. Line 6: prev[j] = True instead of prev[j] = prev[j - 1]

D. Line 17: curr[j] = prev[j - 1]

Solution

1. Step 1: Analyze initialization of prev array for '*' characters

   Line 6 sets prev[j] = True unconditionally when p[j-1] == '*', which incorrectly assumes all prefixes match.

2. Step 2: Correct initialization logic

   It should propagate previous state: prev[j] = prev[j - 1], ensuring '*' can match empty sequence only if previous prefix matched.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incorrect initialization causes false positives on empty strings [OK]

Hint: Initialization must propagate previous True states for '*' [OK]

Common Mistakes:

• Setting prev[j] = True blindly
• Ignoring empty string edge cases
• Confusing '*' handling in initialization

5. Suppose you want to count the number of distinct subsequences of t in s, but now characters in s can be reused multiple times (i.e., you can use the same character in s multiple times to form subsequences). Which modification to the DP approach correctly solves this variant?

hard

A. Use a 2D DP where dp[i][j] counts subsequences using first i chars of s and j chars of t, but allow reusing s[i] by not incrementing i on match

B. Change the recurrence to allow staying at the same i index when matching characters

C. Use the same DP but iterate j forward instead of backward in the inner loop

D. No change needed; original DP already counts subsequences with reuse

Solution

1. Step 1: Understand reuse means characters in s can be used multiple times

   Original DP assumes each character in s can be used at most once per subsequence.

2. Step 2: Modify DP to allow reusing s[i]

   Use 2D DP where dp[i][j] counts subsequences using first i chars of s for first j chars of t, and when s[i] matches t[j], allow staying at i (not incrementing) to reuse character.

3. Step 3: Recognize that iterating j forward or no change won't handle reuse correctly

   Only explicit state allowing reuse by not advancing i on match works.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Allowing reuse requires 2D DP with careful state transitions [OK]

Hint: Reuse means allowing same s[i] multiple times, so must not always increment i

Common Mistakes:

• Assuming original DP handles reuse
• Trying to fix by changing iteration order only