Edit Distance Problem Levenshtein in DSA Go

Mental Model

Find the smallest number of changes needed to turn one word into another by adding, removing, or changing letters.

Analogy: Imagine fixing a typo in a word by either erasing a letter, adding a new one, or changing a wrong letter to the right one, counting each fix as one step.

word1: c a t
word2: c a r

Matrix (rows: word1 letters + empty, cols: word2 letters + empty):
    ''  c   a   r
''  0   1   2   3
c   1   ?   ?   ?
a   2   ?   ?   ?
t   3   ?   ?   ?

Dry Run Walkthrough

Input: word1: "cat", word2: "car"

Goal: Calculate the minimum edits to change "cat" into "car"

Step 1: Initialize first row and column with incremental costs for empty string conversions

    ''  c   a   r
''  0   1   2   3
c   1   ?   ?   ?
a   2   ?   ?   ?
t   3   ?   ?   ?

Why: We need base costs for converting empty string to prefixes

Step 2: Compare 'c' (word1) with 'c' (word2), same letter, cost 0 added

    ''  c   a   r
''  0   1   2   3
c   1   0   ?   ?
a   2   ?   ?   ?
t   3   ?   ?   ?

Why: No edit needed when letters match

Step 3: Compare 'c' with 'a', letters differ, choose min edit among insert, delete, replace

    ''  c   a   r
''  0   1   2   3
c   1   0   1   ?
a   2   ?   ?   ?
t   3   ?   ?   ?

Why: We pick the cheapest way to fix mismatch

Step 4: Compare 'c' with 'r', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   ?   ?   ?
t   3   ?   ?   ?

Why: Continue filling first row for all prefixes

Step 5: Compare 'a' with 'c', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   ?   ?
t   3   ?   ?   ?

Why: Fill second row considering previous costs

Step 6: Compare 'a' with 'a', letters same, cost 0 added

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   ?
t   3   ?   ?   ?

Why: No edit needed for matching letters

Step 7: Compare 'a' with 'r', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   1
t   3   ?   ?   ?

Why: Fill second row completely

Step 8: Compare 't' with 'c', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   1
t   3   2   ?   ?

Why: Start filling last row

Step 9: Compare 't' with 'a', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   1
t   3   2   1   ?

Why: Continue last row

Step 10: Compare 't' with 'r', letters differ, calculate min edit cost

    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   1
t   3   2   1   1

Why: Complete matrix with final edit distance

Result:

Final matrix:
    ''  c   a   r
''  0   1   2   3
c   1   0   1   2
a   2   1   0   1
t   3   2   1   1

Minimum edits needed: 1

Annotated Code

DSA Go

package main

import (
	"fmt"
)

func min(a, b, c int) int {
	if a < b {
		if a < c {
			return a
		}
		return c
	} else {
		if b < c {
			return b
		}
		return c
	}
}

func levenshteinDistance(word1, word2 string) int {
	m := len(word1)
	n := len(word2)
	// Create DP matrix
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}

	// Initialize first row and column
	for i := 0; i <= m; i++ {
		dp[i][0] = i // delete all letters from word1
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j // insert all letters to word1
	}

	// Fill dp matrix
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if word1[i-1] == word2[j-1] {
				dp[i][j] = dp[i-1][j-1] // no edit needed
			} else {
				dp[i][j] = min(
					dp[i-1][j]+1,   // delete
					dp[i][j-1]+1,   // insert
					dp[i-1][j-1]+1, // replace
				)
			}
		}
	}

	return dp[m][n]
}

func main() {
	word1 := "cat"
	word2 := "car"
	distance := levenshteinDistance(word1, word2)
	fmt.Printf("Minimum edits to convert '%s' to '%s': %d\n", word1, word2, distance)
}

for i := 0; i <= m; i++ { dp[i][0] = i // delete all letters from word1 }

initialize first column with cost of deleting letters from word1

for j := 0; j <= n; j++ { dp[0][j] = j // insert all letters to word1 }

initialize first row with cost of inserting letters to word1

if word1[i-1] == word2[j-1] { dp[i][j] = dp[i-1][j-1] // no edit needed } else { dp[i][j] = min( dp[i-1][j]+1, // delete dp[i][j-1]+1, // insert dp[i-1][j-1]+1, // replace ) }

fill dp cell with min cost considering delete, insert, replace or no edit if letters match

Output

Minimum edits to convert 'cat' to 'car': 1

Complexity Analysis

Time: O(m*n) because we fill a matrix of size m by n once

Space: O(m*n) because we store the edit distances for all substring pairs

vs Alternative: Compared to recursive naive approach which is exponential, DP reduces time drastically by storing intermediate results

Edge Cases

One or both strings empty

Distance equals length of the other string (all insertions or deletions)

DSA Go

for i := 0; i <= m; i++ {
	dp[i][0] = i // delete all letters from word1
}

Both strings identical

Distance is zero, no edits needed

DSA Go

if word1[i-1] == word2[j-1] {
	dp[i][j] = dp[i-1][j-1] // no edit needed
}

Strings with all different letters

Distance equals length of longer string if no matches

DSA Go

dp[i][j] = min(
	dp[i-1][j]+1,   // delete
	dp[i][j-1]+1,   // insert
	dp[i-1][j-1]+1, // replace
)

When to Use This Pattern

When asked to find the minimum number of edits to convert one string into another, use the Levenshtein distance dynamic programming pattern to efficiently compute the answer.

Common Mistakes

Mistake: Not initializing the first row and column of the DP matrix
Fix: Explicitly set dp[i][0] = i and dp[0][j] = j to handle empty string conversions

Mistake: Comparing characters with wrong indices causing off-by-one errors
Fix: Use i-1 and j-1 to access characters since dp matrix includes empty prefix row and column

Mistake: Not considering all three operations (insert, delete, replace) when letters differ
Fix: Calculate minimum among dp[i-1][j]+1, dp[i][j-1]+1, and dp[i-1][j-1]+1

Summary

Calculates the minimum number of insertions, deletions, and replacements to convert one string into another.

Use when you need to measure how different two strings are or find the minimal edits to transform one into the other.

The key insight is building a matrix that stores solutions to smaller subproblems, reusing them to solve the full problem 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