Edit Distance Problem Levenshtein in DSA Python - Execution Trace

Concept Flow - Edit Distance Problem Levenshtein

Start with two strings

↓

Create DP table with sizes (len(s1)+1) x (len(s2)+1)

↓

Initialize first row and column

↓

For each cell dp[i

↓

Compare characters s1[i-1

↓

Copy dp[i-1

↓

Fill dp[i

↓

Repeat for all cells

↓

Result is dp[len(s1)

This flow shows how the DP table is built step-by-step comparing characters and filling minimum edit operations.

Execution Sample

DSA Python

s1 = "kitten"
s2 = "sitting"
# Initialize dp table
dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]

# Initialize first row and column
for i in range(len(s1) + 1):
    dp[i][0] = i
for j in range(len(s2) + 1):
    dp[0][j] = j

# Compute dp table for edit distance
for i in range(1, len(s1) + 1):
    for j in range(1, len(s2) + 1):
        if s1[i - 1] == s2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = 1 + min(dp[i - 1][j],    # delete
                               dp[i][j - 1],    # insert
                               dp[i - 1][j - 1]) # replace

This code computes the edit distance table for strings 'kitten' and 'sitting'.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table State (partial)
1	Initialize dp[0][0]	(0,0)	N/A	0	[[0, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _], [_, _, _, _, _, _, _, _]]
2	Initialize first row dp[0][j]	(0,1)	N/A	1	[[0, 1, _, _, _, _, _, _], ...]
3	Initialize first row dp[0][j]	(0,2)	N/A	2	[[0, 1, 2, _, _, _, _, _], ...]
4	Initialize first row dp[0][j]	(0,3)	N/A	3	[[0, 1, 2, 3, _, _, _, _], ...]
5	Initialize first row dp[0][j]	(0,4)	N/A	4	[[0, 1, 2, 3, 4, _, _, _], ...]
6	Initialize first row dp[0][j]	(0,5)	N/A	5	[[0, 1, 2, 3, 4, 5, _, _], ...]
7	Initialize first row dp[0][j]	(0,6)	N/A	6	[[0, 1, 2, 3, 4, 5, 6, _], ...]
8	Initialize first row dp[0][j]	(0,7)	N/A	7	[[0, 1, 2, 3, 4, 5, 6, 7], ...]
9	Initialize first column dp[i][0]	(1,0)	N/A	1	[[0, 1, 2, 3, 4, 5, 6, 7], [1, _, _, _, _, _, _, _], ...]
10	Compare s1[0]='k' and s2[0]='s'	(1,1)	'k' vs 's'	1	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, _, _, _, _, _, _], ...]
11	Compare s1[0]='k' and s2[1]='i'	(1,2)	'k' vs 'i'	2	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, _, _, _, _, _], ...]
12	Compare s1[0]='k' and s2[2]='t'	(1,3)	'k' vs 't'	3	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, _, _, _, _], ...]
13	Compare s1[0]='k' and s2[3]='t'	(1,4)	'k' vs 't'	4	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, 4, _, _, _], ...]
14	Compare s1[0]='k' and s2[4]='i'	(1,5)	'k' vs 'i'	5	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, 4, 5, _, _], ...]
15	Compare s1[0]='k' and s2[5]='n'	(1,6)	'k' vs 'n'	6	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, 4, 5, 6, _], ...]
16	Compare s1[0]='k' and s2[6]='g'	(1,7)	'k' vs 'g'	7	[[0, 1, 2, 3, 4, 5, 6, 7], [1, 1, 2, 3, 4, 5, 6, 7], ...]
17	Compare s1[1]='i' and s2[0]='s'	(2,1)	'i' vs 's'	2	...
18	Compare s1[1]='i' and s2[1]='i'	(2,2)	'i' vs 'i'	1	...
19	Compare s1[1]='i' and s2[2]='t'	(2,3)	'i' vs 't'	2	...
20	Compare s1[2]='t' and s2[2]='t'	(3,3)	't' vs 't'	1	...
21	Compare s1[5]='n' and s2[5]='n'	(6,6)	'n' vs 'n'	1	...
22	Final result dp[6][7]	(6,7)	N/A	3	Full dp table filled
23	Exit	N/A	N/A	N/A	All dp cells computed, minimum edit distance is 3

💡 All dp cells computed, minimum edit distance is dp[len(s1)][len(s2)] = 3

Variable Tracker

Variable	Start	After Step 10	After Step 18	After Step 22	Final
i	0	1	2	6	6
j	0	1	2	7	7
dp[0][0]	0	0	0	0	0
dp[1][1]	undefined	1	1	1	1
dp[2][2]	undefined	undefined	1	1	1
dp[6][7]	undefined	undefined	undefined	3	3

Key Moments - 3 Insights

Why do we initialize the first row and first column of the dp table?

The first row and column represent converting from or to an empty string, so their values are the number of insertions or deletions needed. This is shown in execution_table rows 2-8 and 9.

Why do we add 1 when characters do not match?

When characters differ, we consider the minimum of insert, delete, or replace operations plus 1 for the current operation. This is shown in execution_table rows 10-22 where mismatches increase dp values.

Why is the final answer at dp[len(s1)][len(s2)]?

Because dp[i][j] stores the minimum edits to convert first i chars of s1 to first j chars of s2, so dp[len(s1)][len(s2)] is the full strings' edit distance, as in execution_table row 22.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the dp cell value for dp[1][1] comparing 'k' and 's'?

A 1

B 0

C 2

D Undefined

💡 Hint

Refer to execution_table row 10 under 'DP Cell Value'

At which step does the dp cell value first become 1 when characters match?

A Step 10

B Step 18

C Step 22

D Step 2

💡 Hint

Check execution_table rows 17-19 for character matches and dp values

If we changed s2 to 'kitten', what would be the dp[6][6] value?

A 6

B 3

C 0

D 1

💡 Hint

If strings are identical, edit distance is zero; check concept_snapshot

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits (insert, delete, replace) to convert one string to another.
Use a DP table dp of size (len(s1)+1) x (len(s2)+1).
Initialize first row and column with 0..n (edits to/from empty string).
Fill dp[i][j] by comparing s1[i-1] and s2[j-1]:
  if equal, dp[i][j] = dp[i-1][j-1]
  else dp[i][j] = 1 + min(insert, delete, replace)
Result is dp[len(s1)][len(s2)].

Full Transcript

The Edit Distance Problem (Levenshtein) calculates the minimum number of edits needed to change one string into another. We use a table called dp where each cell dp[i][j] represents the minimum edits to convert the first i characters of the first string into the first j characters of the second string. We start by filling the first row and column because converting to or from an empty string requires a number of insertions or deletions equal to the length. Then, for each cell, we compare the characters from both strings. If they match, we copy the diagonal value. If not, we take the minimum of three possible operations (insert, delete, replace) plus one. After filling the table, the bottom-right cell gives the answer. This method ensures we consider all possibilities efficiently.

Practice

1. What does the Edit Distance (Levenshtein distance) between two strings measure?

easy

A. The minimum number of single-character edits to change one string into the other

B. The number of common characters between two strings

C. The length of the longest common substring

D. The number of characters in the longer string

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts how many changes (insert, delete, replace) are needed to convert one string to another.

2. Step 2: Compare options with definition

   Only The minimum number of single-character edits to change one string into the other correctly describes this minimum number of single-character edits.

3. Final Answer:

   The minimum number of single-character edits to change one string into the other -> Option A

4. Quick Check:

   Edit Distance = minimum edits [OK]

Hint: Edit Distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing with longest common substring
• Thinking it counts common characters
• Assuming it measures string length

2. Which of the following Python code snippets correctly initializes a 2D list for dynamic programming of size (m+1) x (n+1)?

easy

A. dp = [0] * (m+1) * (n+1)

B. dp = [[0] * (n+1) for _ in range(m+1)]

C. dp = [[0] * m for _ in range(n)]

D. dp = [[0] * (m+1)] * (n+1)

Solution

1. Step 1: Understand 2D list initialization in Python

   Using list comprehension with separate inner lists avoids shared references.

2. Step 2: Analyze each option

   dp = [[0] * (n+1) for _ in range(m+1)] correctly creates independent rows. dp = [[0] * (m+1)] * (n+1) creates shallow copies causing bugs. Options A and C have wrong dimensions or types.

3. Final Answer:

   dp = [[0] * (n+1) for _ in range(m+1)] -> Option B

4. Quick Check:

   Proper 2D list init = dp = [[0] * (n+1) for _ in range(m+1)] [OK]

Hint: Use list comprehension for 2D lists to avoid shared rows [OK]

Common Mistakes:

• Using multiplication for 2D lists causing shared references
• Mixing up m and n dimensions
• Creating 1D list instead of 2D

3. What is the output of the following Python code snippet that calculates the Levenshtein distance between 'kitten' and 'sitting'?

def levenshtein(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

print(levenshtein('kitten', 'sitting'))

medium

A. 4

B. 5

C. 3

D. 6

Solution

1. Step 1: Understand the Levenshtein distance calculation

   Compare 'kitten' and 'sitting' stepwise counting minimal edits: substitute 'k'->'s' (kitten -> sitten), substitute 'e'->'i' (sitten -> sittin), insert 'g' at end (sittin -> sitting). Total 3 edits.

2. Step 2: Verify with code logic

   The code correctly implements the DP approach and returns dp[m][n] which is 3 for these inputs.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Levenshtein('kitten','sitting') = 3 [OK]

Hint: Count minimal edits: replace, insert, delete [OK]

Common Mistakes:

• Counting only replacements, ignoring insertions
• Miscounting characters to change
• Confusing with substring length

4. Identify the bug in this Levenshtein distance code snippet:

def levenshtein_bug(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0] * (n+1)] * (m+1)
    for i in range(m+1):
        dp[i][0] = i
    for j in range(n+1):
        dp[0][j] = j
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

medium

A. Using dp = [[0] * (n+1)] * (m+1) causes all rows to reference the same list

B. The loops should start from 0 instead of 1

C. The condition s1[i-1] == s2[j-1] should be s1[i] == s2[j]

D. The return statement should be dp[0][0]

Solution

1. Step 1: Analyze dp initialization

   Using multiplication to create dp causes all rows to point to the same list, so updating one row updates all rows.

2. Step 2: Understand impact on algorithm

   This shared reference breaks the DP table updates, causing incorrect results.

3. Final Answer:

   Using dp = [[0] * (n+1)] * (m+1) causes all rows to reference the same list -> Option A

4. Quick Check:

   Shared row references cause bugs [OK]

Hint: Avoid list multiplication for 2D lists; use list comprehension [OK]

Common Mistakes:

• Using wrong dp initialization
• Incorrect loop ranges
• Wrong indexing in condition

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the minimum edit distance using Levenshtein algorithm? Consider insert, delete, and replace operations each cost 1.

hard

A. 7

B. 5

C. 4

D. 6

Solution

1. Step 1: Compare strings and count minimal edits

   Transform 'intention' to 'execution' requires the minimum number of single-character edits (insertions, deletions, substitutions) of 6.

2. Step 2: Confirm with Levenshtein DP logic

   Dynamic programming confirms minimum edits as 6 for these strings.

3. Final Answer:

   6 -> Option D

4. Quick Check:

   Levenshtein('intention','execution') = 6 [OK]

Hint: Count replacements and insertions carefully for longer strings [OK]

Common Mistakes:

• Underestimating number of replacements
• Ignoring insertions
• Confusing with Hamming distance