Edit Distance Problem Levenshtein in DSA Go - Execution Trace

Concept Flow - Edit Distance Problem Levenshtein

Start with two strings

↓

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

↓

Initialize first row and column with 0..n

↓

For each cell (i,j):

↓

Compare s1[i-1

↓

Copy diagonal

↓

Fill table row by row

↓

Result is value at bottom-right cell

↓

Minimum edits needed

This flow shows how we build a table to find the minimum edits to convert one string into another by comparing characters and filling the table step-by-step.

Execution Sample

DSA Go

s1 := "kitten"
s2 := "sitting"
// Create dp table
// Fill first row and column
// Fill rest with min edits
// Result dp[len(s1)][len(s2)]

This code calculates the minimum number of edits to change "kitten" into "sitting" using a DP table.

Execution Table

Step	Operation	Cell (i,j)	Characters Compared	DP Table State	Pointer Changes	Visual State
1	Initialize DP table	(0,0)	N/A	[[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0]]	Set head pointer	Empty table with 7 rows and 8 columns
2	Fill first row	(0,j)	N/A	[[0,1,2,3,4,5,6,7],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0]]	Move right along row 0	First row filled with 0 to 7
3	Fill first column	(i,0)	N/A	[[0,1,2,3,4,5,6,7],[1,0,0,0,0,0,0,0],[2,0,0,0,0,0,0,0],[3,0,0,0,0,0,0,0],[4,0,0,0,0,0,0,0],[5,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0]]	Move down along column 0	First column filled with 0 to 6
4	Compare chars	(1,1)	k vs s	[[0,1,2,3,4,5,6,7],[1,1,0,0,0,0,0,0],[2,0,0,0,0,0,0,0],[3,0,0,0,0,0,0,0],[4,0,0,0,0,0,0,0],[5,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0]]	Check diagonal (0), left (1), top (1)	Cell (1,1) set to 1 (min+1)
5	Compare chars	(1,2)	k vs i	[[0,1,2,3,4,5,6,7],[1,1,2,0,0,0,0,0],[2,0,0,0,0,0,0,0],[3,0,0,0,0,0,0,0],[4,0,0,0,0,0,0,0],[5,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0]]	Check diagonal (1), left (1), top (2)	Cell (1,2) set to 2
6	Compare chars	(1,3)	k vs t	[[0,1,2,3,4,5,6,7],[1,1,2,3,0,0,0,0],[2,0,0,0,0,0,0,0],[3,0,0,0,0,0,0,0],[4,0,0,0,0,0,0,0],[5,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0]]	Check diagonal (2), left (2), top (3)	Cell (1,3) set to 3
7	Compare chars	(2,1)	i vs s	[[0,1,2,3,4,5,6,7],[1,1,2,3,4,0,0,0],[2,2,0,0,0,0,0,0],[3,0,0,0,0,0,0,0],[4,0,0,0,0,0,0,0],[5,0,0,0,0,0,0,0],[6,0,0,0,0,0,0,0]]	Check diagonal (1), left (2), top (1)	Cell (2,1) set to 2
8	Compare chars	(6,7)	n vs g	[[0,1,2,3,4,5,6,7],[1,1,2,3,4,5,6,7],[2,2,1,2,3,4,5,6],[3,3,2,1,2,3,4,5],[4,4,3,2,2,2,3,4],[5,5,4,3,3,3,2,3],[6,6,5,4,4,4,3,3]]	Check diagonal (2), left (3), top (3)	Cell (6,7) set to 3
9	Final result	(6,7)	N/A	Final DP table as above	No pointer change	Minimum edits needed: 3

💡 All cells filled; bottom-right cell (6,7) contains minimum edit distance 3

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 8	Final
dp	empty 7x8 zeros	first row filled 0..7	first column filled 0..6	partial fill with first comparisons	mostly filled with min edits	fully filled with final edit distances
i	0	0	1	1	6	6
j	0	1	0	1	7	7
current cell value	0	1	1	1	3	3

Key Moments - 3 Insights

Why do we initialize the first row and first column with increasing numbers?

Because converting an empty string to a string of length n requires n insertions or deletions. This is shown in execution_table rows 2 and 3 where the first row and column are filled with 0 to length values.

Why do we take the minimum of left, top, and diagonal cells plus one when characters differ?

Because these represent the three operations: insert, delete, and replace. We pick the cheapest operation plus one edit. This is shown in execution_table rows 4 to 6 where the cell value is set to min(left, top, diagonal) + 1.

What does the bottom-right cell in the DP table represent?

It represents the minimum number of edits needed to convert the entire first string into the second string. This is shown in execution_table row 9 where the final answer 3 is stored.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value set in cell (1,1)?

A 0

B 2

C 1

D 3

💡 Hint

Check execution_table row with Step 4 under 'Visual State' column

At which step does the DP table first get the value 3 in any cell?

A Step 3

B Step 6

C Step 8

D Step 9

💡 Hint

Look at execution_table rows and find when cell value 3 appears first

If the first string was empty, how would the first column of the DP table change?

A It would remain all zeros

B It would be filled with increasing numbers from 0 to length of second string

C It would be filled with decreasing numbers

D It would be filled with random values

💡 Hint

Refer to variable_tracker row for dp and execution_table rows 2 and 3

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits (insert, delete, replace) to convert one string to another.
Use a DP table of size (len(s1)+1) x (len(s2)+1).
Initialize first row and column with 0..n.
Fill each cell by comparing chars: if equal, copy diagonal; else min(left, top, diagonal)+1.
Result is bottom-right cell value.
Time complexity: O(m*n).

Full Transcript

The Edit Distance Problem, also called Levenshtein distance, calculates the minimum number of edits needed to change one string into another. We use a table with rows for each character of the first string plus one, and columns for the second string plus one. We fill the first row and column with increasing numbers because converting an empty string to a string of length n requires n insertions or deletions. Then, for each cell, we compare the characters from both strings. If they are the same, we copy the diagonal cell value. If not, we take the minimum of the left, top, and diagonal cells plus one, representing insert, delete, or replace operations. The final answer is in the bottom-right cell of the table. This method ensures we find the minimum edits efficiently.

Practice

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

easy

A. The number of matching characters in the same positions

B. The number of characters in the longer string

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

D. The length difference between the two strings

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: Identify what is measured

   It measures the minimum number of single-character edits required.

3. Final Answer:

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

4. Quick Check:

   Edit Distance = minimum edits [OK]

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

Common Mistakes:

• Confusing edit distance with string length
• Thinking it counts only matching characters
• Assuming it measures length difference only

2. Which of the following Go function signatures correctly represents a function to compute Levenshtein distance between two strings s1 and s2?

easy

A. func Levenshtein(s1, s2 string) string

B. func Levenshtein(s1, s2 string) int

C. func Levenshtein(s1 int, s2 int) string

D. func Levenshtein(s1, s2 int) int

Solution

1. Step 1: Identify input types for strings

   The function must accept two strings as input parameters.

2. Step 2: Identify output type

   The output is an integer representing the edit distance.

3. Final Answer:

   func Levenshtein(s1, s2 string) int -> Option B

4. Quick Check:

   Input: strings, Output: int [OK]

Hint: Function inputs are strings, output is int distance [OK]

Common Mistakes:

• Using int instead of string for inputs
• Returning string instead of int
• Mixing input types incorrectly

3. What is the output of the following Go code snippet computing Levenshtein distance between "kitten" and "sitting"?

package main
import "fmt"
func main() {
    s1 := "kitten"
    s2 := "sitting"
    dist := Levenshtein(s1, s2)
    fmt.Println(dist)
}

func Levenshtein(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            cost := 0
            if a[i-1] != b[j-1] {
                cost = 1
            }
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
        }
    }
    return dp[m][n]
}

func min(x, y, z int) int {
    if x < y {
        if x < z {
            return x
        }
        return z
    }
    if y < z {
        return y
    }
    return z
}

medium

A. 6

B. 4

C. 5

D. 3

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions k->s, e->i, plus insert g.

2. Step 2: Calculate minimum edits

   Minimum edits are 2 substitutions + 1 insertion = 3 edits total.

3. Final Answer:

   3 -> Option D

4. Quick Check:

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

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Counting only substitutions
• Ignoring insertions
• Miscounting character positions

4. Identify the bug in this Go function computing Levenshtein distance:

func Levenshtein(a, b string) int {
    m, n := len(a), len(b)
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    for i := 0; i < m; i++ {
        dp[i][0] = i
    }
    for j := 0; j < n; j++ {
        dp[0][j] = j
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            cost := 0
            if a[i-1] != b[j-1] {
                cost = 1
            }
            dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+cost)
        }
    }
    return dp[m-1][n-1]
}

medium

A. dp slice sizes should be m+1 and n+1, not m and n

B. The cost calculation should be outside the loops

C. The min function is missing

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

Solution

1. Step 1: Check dp slice initialization

   dp must have size m+1 by n+1 to include empty string cases, but code uses m and n only.

2. Step 2: Understand impact of wrong sizes

   Using m and n causes index out of range errors and incorrect base cases.

3. Final Answer:

   dp slice sizes should be m+1 and n+1, not m and n -> Option A

4. Quick Check:

   dp size = m+1, n+1 [OK]

Hint: dp array must cover empty prefixes with +1 size [OK]

Common Mistakes:

• Initializing dp with wrong sizes
• Misplacing cost calculation
• Returning wrong dp cell

5. Given two strings s1 = "intention" and s2 = "execution", what is the minimum edit distance using Levenshtein algorithm? Consider insertions, deletions, and substitutions only.

hard

A. 6

B. 5

C. 8

D. 7

Solution

1. Step 1: Analyze differences between "intention" and "execution"

   Compare characters and count edits: substitutions and insertions/deletions as needed.

2. Step 2: Calculate minimal edits

   Minimum edits calculated are 6 total.

3. Final Answer:

   6 -> Option A

4. Quick Check:

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

Hint: Count substitutions plus insertions/deletions carefully [OK]

Common Mistakes:

• Underestimating substitutions
• Ignoring insertions/deletions
• Confusing character positions