Edit Distance

▶

Steps

setup

Initialize lengths and next_row array

We calculate the lengths of word1 and word2, then initialize the next_row array with zeros. This array will hold the DP values for the suffix starting beyond the last character of word1.

💡 Setting up lengths and the DP array is essential to prepare for bottom-up computation of edit distances.

Line:

m, n = len(word1), len(word2)
next_row = [0] * (n + 1)

💡 The DP arrays have size n+1 to handle empty suffixes of word2.

fill_row

Fill next_row with base case values

We fill next_row with the cost of converting an empty suffix of word1 to suffixes of word2. This is simply the number of characters left in word2 to insert.

💡 This base case sets the cost when word1 is empty, which is the length of the remaining word2 suffix.

Line:

for j in range(n + 1):
    next_row[j] = n - j

💡 The DP array now represents the cost of inserting characters to match word2 suffixes.

traverse

Process i=4 ('e') row: initialize and compute DP values

Initialize current array for i=4 and set current[n] to cost of deleting remaining characters. Then compute current[j] for j=2,1,0 by comparing characters and choosing minimal edit operations.

💡 Processing from the end allows bottom-up DP to build solutions for smaller suffixes first.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 The DP formula combines insert, delete, and replace costs to find minimal edits.

expand

Swap current and next_row arrays after i=4

Assign current to next_row to prepare for next iteration with i=3.

💡 Swapping arrays saves space and moves the DP computation forward.

Line:

next_row = current

💡 The next_row now holds the latest DP results for suffix starting at i=4.

traverse

Process i=3 ('s') row: initialize and compute DP values

Initialize current array for i=3 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Each new row starts with base deletion cost for suffix of word1.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 Matching characters allow carrying forward previous cost without increment.

expand

Swap current and next_row arrays after i=3

Assign current to next_row for next iteration with i=2.

💡 Swapping arrays moves the DP computation forward efficiently.

Line:

next_row = current

💡 Next_row now holds DP results for suffix starting at i=3.

traverse

Process i=2 ('r') row: initialize and compute DP values

Initialize current array for i=2 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Each row starts with deletion cost for suffix of word1.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 Matching characters reduce edit distance by carrying forward previous costs.

expand

Swap current and next_row arrays after i=2

Assign current to next_row for next iteration with i=1.

💡 Moving DP computation forward.

Line:

next_row = current

💡 Next_row holds DP results for suffix starting at i=2.

traverse

Process i=1 ('o') row: initialize and compute DP values

Initialize current array for i=1 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Starting new DP row with deletion cost.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 DP combines three possible operations to find minimal cost.

expand

Swap current and next_row arrays after i=1

Assign current to next_row for next iteration with i=0.

💡 Moving DP computation forward.

Line:

next_row = current

💡 Next_row holds DP results for suffix starting at i=1.

traverse

Process i=0 ('h') row: initialize and compute DP values

Initialize current array for i=0 and set current[n] to deletion cost. Compute current[j] for j=2,1,0 comparing characters and choosing minimal edits.

💡 Starting new DP row with deletion cost.

Line:

current = [0] * (n + 1)
current[n] = m - i
for j in range(n - 1, -1, -1):
    if word1[i] == word2[j]:
        current[j] = next_row[j + 1]
    else:
        current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])

💡 DP row fully computed for i=0.

reconstruct

Final swap and read answer

Assign current to next_row and return next_row[0] as the minimum edit distance between the full strings.

💡 The answer is the minimal edits to convert word1 to word2.

Line:

next_row = current
return next_row[0]

💡 The DP solution is complete and the answer is at next_row[0].

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)  # STEP 1
    next_row = [0] * (n + 1)  # STEP 1
    for j in range(n + 1):  # STEP 2
        next_row[j] = n - j  # STEP 2

    for i in range(m - 1, -1, -1):  # STEPS 3,5,7,9,11
        current = [0] * (n + 1)  # STEPS 3,5,7,9,11
        current[n] = m - i  # STEPS 3,5,7,9,11
        for j in range(n - 1, -1, -1):  # Inner loop
            if word1[i] == word2[j]:  # Character match
                current[j] = next_row[j + 1]
            else:
                current[j] = 1 + min(current[j + 1], next_row[j], next_row[j + 1])
        next_row = current  # Swap rows

    return next_row[0]  # STEP 12

📊

Edit Distance - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the algorithm builds solutions for smaller suffixes and combines them to solve the full problem, making the dynamic programming approach intuitive.

setup

0

0

0

1

0

2

n

0

3

fill_row

j

3

0

2

1

1

2

0

3

compare

3

0

2

1

1

2

1

3

move_left

3

0

2

1

1

2

i

1

3

compare

3

0

2

1

1

2

i

2

3

move_left

3

0

2

1

i

1

2

2

3

compare

2

0

3

1

i

3

2

3

3

move_left

2

0

i

3

1

3

2

3

3

compare

3

0

i

3

1

4

2

4

3

move_left

i

3

0

3

1

4

2

4

3

compare

i

4

0

4

1

5

2

5

3

record

answer

3

0

2

1

1

2

1

3

Result: 3

Key Takeaways

✓ The DP arrays represent minimal edit distances for suffixes of the strings, computed bottom-up.

This insight is hard to see from code alone because the arrays are reused and updated in place.

✓ Matching characters allow the algorithm to carry forward previous costs without adding edits.

Seeing this visually clarifies why some DP cells copy values instead of adding 1.

✓ Each DP cell chooses the minimal cost among insert, delete, and replace operations, illustrating the decision process.

Watching the min calculation step-by-step reveals how the algorithm balances different edit operations.

Practice

1. You are given a string and need to count all substrings that read the same forwards and backwards. Which approach guarantees an optimal time and space solution for this problem?

easy

A. Use a brute force approach checking every substring with nested loops and palindrome verification.

B. Use a longest common subsequence DP approach comparing the string with its reverse.

C. Expand around each character and each pair of characters to count palindromes in O(n²) time and O(1) space.

D. Apply a greedy approach by extending palindromes only when characters match at the ends.

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all palindromic substrings efficiently, not just longest palindromes.

2. Step 2: Evaluate approaches

   Brute force is correct but inefficient (O(n³)). LCS DP finds longest palindrome but not count of all substrings. Greedy fails on nested palindromes. Expanding around centers counts all palindromes in O(n²) time and O(1) space.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Expanding around centers covers odd and even length palindromes efficiently [OK]

Hint: Expanding centers counts all palindromes in O(n²) time [OK]

Common Mistakes:

• Confusing longest palindrome with counting all palindromic substrings

2. What is the time complexity of the optimal space-optimized dynamic programming solution for counting distinct subsequences of t in s, where m = len(s) and n = len(t)?

medium

A. O(m + n)

B. O(2^m)

C. O(m * n)

D. O(m * n^2)

Solution

1. Step 1: Identify nested loops over s and t

   The code iterates over all characters of s (m times) and for each, iterates over t (n times) in reverse order.

2. Step 2: Calculate total operations

   Each iteration does O(1) work, so total time is O(m * n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Two nested loops over lengths m and n -> O(m*n) [OK]

Hint: Nested loops over s and t imply O(m*n) time [OK]

Common Mistakes:

• Confusing recursion exponential time with DP time
• Ignoring nested loop structure

3. What is the time and space complexity of the space-optimized bottom-up dynamic programming solution for the Longest Common Subsequence problem, where the input strings have lengths m and n respectively?

medium

A. Time: O(m*n), Space: O(m*n)

B. Time: O(m+n), Space: O(m+n)

C. Time: O(m*n), Space: O(n)

D. Time: O(2^(m+n)), Space: O(m+n)

Solution

1. Step 1: Identify time complexity

   The algorithm uses two nested loops: outer loop runs m times, inner loop runs n times, resulting in O(m*n) time.

2. Step 2: Identify space complexity

   Space optimized DP uses a single array of size n+1, so space complexity is O(n). The recursion stack or full DP table is not used.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops give O(m*n) time; single dp array gives O(n) space [OK]

Hint: Nested loops multiply time; single dp array reduces space [OK]

Common Mistakes:

• Confusing full DP table space with optimized space
• Assuming linear time due to single dp array
• Forgetting recursion stack space in brute force

4. What is the time complexity of the bottom-up DP solution for Word Break II that uses nested loops over the string and dictionary words, and concatenates sentences stored in dp arrays?

medium

A. O(n^3) due to nested loops and string concatenations

B. O(n^2 * m) because each substring is checked against dictionary words

C. O(2^n) because all segmentations are explored

D. O(n * m) where n = length of string, m = number of words in dictionary

Solution

1. Step 1: Identify nested loops and operations

   Outer loop runs n times, inner loop over dictionary words m times, and for each match, concatenation of strings from dp arrays occurs.

2. Step 2: Analyze concatenation cost

   Concatenation and copying sentences can cost up to O(n) each, and there can be O(n^2) substrings, leading to O(n^3) total time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops plus string concatenations cause cubic time [OK]

Hint: String concatenation inside nested loops causes O(n^3) [OK]

Common Mistakes:

• Confusing exponential brute force with DP complexity
• Ignoring concatenation cost

5. The following code attempts to solve Word Break II using bottom-up DP. Identify the line containing the subtle bug that causes incorrect output with extra spaces in the sentences.

medium

A. Line: for word in word_set:

B. Line: sentences.append(word + " " + sentence)

C. Line: dp[n] = [""]

D. Line: if s.startswith(word, i):

Solution

1. Step 1: Examine string concatenation logic

   The line appends word + " " + sentence unconditionally, causing extra spaces when sentence is empty (base case).

2. Step 2: Identify fix

   Concatenate with space only if sentence is non-empty; otherwise append word alone to avoid trailing spaces.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Extra spaces come from unconditional space concatenation [OK]

Hint: Check concatenation when sentence is empty to avoid extra spaces [OK]

Common Mistakes:

• Forgetting base case empty string concatenation
• Misusing string concatenation in DP