Edit Distance Problem Levenshtein in DSA C#

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, writing a new letter, or changing a wrong letter to the right one, counting each fix as one step.

word1: c a t
word2: c a r

Start comparing letters from left to right:
 c -> c
 a -> a
 t -> r

Each difference means a change needed.

Dry Run Walkthrough

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

Goal: Find the minimum number of edits to change "cat" into "car"

Step 1: Compare last letters 't' and 'r', they differ, so consider substitution cost 1

Matrix partial:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 [1]

Why: We check if changing 't' to 'r' costs less than adding or deleting

Step 2: Calculate cost for changing 'a' to 'a' (same letter), cost 0

Matrix partial:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 1

Why: No edit needed for matching letters

Step 3: Calculate cost for changing 'c' to 'c' (same letter), cost 0

Matrix final:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 1

Why: No edit needed for matching letters

Result:

Minimum edit distance is 1
Final matrix:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 1

Annotated Code

DSA C#

using System;

class EditDistance {
    public static int LevenshteinDistance(string s1, string s2) {
        int m = s1.Length;
        int n = s2.Length;
        int[,] dp = new int[m + 1, n + 1];

        // Initialize base cases for empty strings
        for (int i = 0; i <= m; i++) {
            dp[i, 0] = i; // delete all characters from s1
        }
        for (int j = 0; j <= n; j++) {
            dp[0, j] = j; // insert all characters to s1
        }

        // Fill dp matrix
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1[i - 1] == s2[j - 1]) {
                    dp[i, j] = dp[i - 1, j - 1]; // no change needed
                } else {
                    dp[i, j] = Math.Min(
                        dp[i - 1, j] + 1,    // delete
                        Math.Min(
                            dp[i, j - 1] + 1,  // insert
                            dp[i - 1, j - 1] + 1 // substitute
                        )
                    );
                }
            }
        }
        return dp[m, n];
    }

    static void Main() {
        string word1 = "cat";
        string word2 = "car";
        int distance = LevenshteinDistance(word1, word2);
        Console.WriteLine(distance);
    }
}

for (int i = 0; i <= m; i++) { dp[i, 0] = i; }

initialize cost of deleting all characters from s1 to match empty s2

for (int j = 0; j <= n; j++) { dp[0, j] = j; }

initialize cost of inserting all characters to s1 to match s2

if (s1[i - 1] == s2[j - 1]) { dp[i, j] = dp[i - 1, j - 1]; }

no edit needed if characters match, carry over previous cost

dp[i, j] = Math.Min(dp[i - 1, j] + 1, Math.Min(dp[i, j - 1] + 1, dp[i - 1, j - 1] + 1));

choose minimum cost among delete, insert, or substitute

Output

1

Complexity Analysis

Time: O(m*n) because we fill a matrix of size m by n comparing all character pairs

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

vs Alternative: Compared to recursive solutions without memoization which are exponential, this dynamic programming approach is efficient and practical

Edge Cases

One or both strings empty

Distance equals the length of the non-empty string (all insertions or deletions)

DSA C#

for (int i = 0; i <= m; i++) { dp[i, 0] = i; }

Both strings are the same

Distance is zero because no edits are needed

DSA C#

if (s1[i - 1] == s2[j - 1]) { dp[i, j] = dp[i - 1, j - 1]; }

Strings with repeated characters

Algorithm correctly counts edits considering each character position

DSA C#

dp[i, j] = Math.Min(...)

When to Use This Pattern

When you need to measure how different two strings are by counting edits, use the Levenshtein distance dynamic programming pattern to find the minimum changes efficiently.

Common Mistakes

Mistake: Forgetting to initialize the first row and column of the dp matrix
Fix: Add loops to set dp[i,0] = i and dp[0,j] = j to handle empty string cases

Mistake: Using wrong indices when accessing characters (off by one)
Fix: Use s1[i-1] and s2[j-1] because dp indices start from 1 but strings from 0

Summary

Calculates the minimum number of insertions, deletions, or substitutions to convert one string into another.

Use when you want to find how similar or different two strings are by counting edits.

The key insight is building a matrix that stores solutions for smaller parts and combines them to solve the full problem.

Practice

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

easy

A. The total length of both strings combined

B. The maximum length of common substring between two strings

C. The number of characters that are the same in both strings

D. The minimum number of single-character edits to change one string into another

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It counts the minimum edits (insertions, deletions, substitutions) to convert one string into another.

2. Step 2: Compare with other options

   Options B and C describe different string metrics, not edit distance.

3. Final Answer:

   The minimum number of single-character edits to change one string into another -> Option D

4. Quick Check:

   Edit distance = minimum edits [OK]

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

Common Mistakes:

• Confusing edit distance with longest common substring
• Thinking it counts only substitutions
• Assuming it measures string length

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

easy

A. private string LevenshteinDistance(string s1, string s2)

B. public void LevenshteinDistance(int s1, int s2)

C. public int LevenshteinDistance(string s1, string s2)

D. public int LevenshteinDistance(int[] s1, int[] s2)

Solution

1. Step 1: Check parameter types for string inputs

   The function should accept two strings, so parameters must be string types.

2. Step 2: Check return type for distance value

   Distance is an integer, so return type should be int, not void or string.

3. Final Answer:

   public int LevenshteinDistance(string s1, string s2) -> Option C

4. Quick Check:

   Function signature matches string inputs and int output [OK]

Hint: Function takes strings, returns int distance [OK]

Common Mistakes:

• Using void return type instead of int
• Using int parameters instead of strings
• Returning string instead of int

3. What is the output of the following C# code snippet?

var s1 = "kitten";
var s2 = "sitting";
Console.WriteLine(LevenshteinDistance(s1, s2));

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length + 1, b.Length + 1];
    for (int i = 0; i <= a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j <= b.Length; j++) dp[0, j] = j;
    for (int i = 1; i <= a.Length; i++) {
        for (int j = 1; j <= b.Length; j++) {
            int cost = (a[i - 1] == b[j - 1]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length, b.Length];
}

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions, insertions, deletions.

2. Step 2: Calculate Levenshtein distance manually

   Changes: k->s (substitution), e->i (substitution), t->t (no change), t->t (no change), e->i (substitution), n->n (no change), add g (insertion) = 3 substitutions + 1 insertion = 4 edits total.

3. Final Answer:

   4 -> Option B

4. Quick Check:

   Distance("kitten", "sitting") = 4 [OK]

Hint: Remember common example: kitten -> sitting = 4 edits [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions
• Miscounting character positions
• Confusing with Hamming distance

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

int LevenshteinDistance(string a, string b) {
    int[,] dp = new int[a.Length, b.Length];
    for (int i = 0; i < a.Length; i++) dp[i, 0] = i;
    for (int j = 0; j < b.Length; j++) dp[0, j] = j;
    for (int i = 1; i < a.Length; i++) {
        for (int j = 1; j < b.Length; j++) {
            int cost = (a[i] == b[j]) ? 0 : 1;
            dp[i, j] = Math.Min(Math.Min(dp[i - 1, j] + 1, dp[i, j - 1] + 1), dp[i - 1, j - 1] + cost);
        }
    }
    return dp[a.Length - 1, b.Length - 1];
}

medium

A. Array size should be (a.Length+1, b.Length+1) and loops adjusted

B. Cost calculation should use a[i-1] and b[j-1]

C. Return statement should be dp[a.Length, b.Length]

D. No bug, code is correct

Solution

1. Step 1: Check array size and indexing

   dp array must be sized (a.Length+1, b.Length+1) to include empty prefixes; current size misses last row/column.

2. Step 2: Adjust loops to run from 0 to length inclusive

   Loops should run to <= length to fill dp correctly; current loops miss last indices.

3. Final Answer:

   Array size should be (a.Length+1, b.Length+1) and loops adjusted -> Option A

4. Quick Check:

   dp array size must include empty string row/column [OK]

Hint: dp array must be one larger than string lengths [OK]

Common Mistakes:

• Using array size equal to string length only
• Incorrect loop bounds causing index errors
• Ignoring empty string base cases

5. Given two strings s1 = "intention" and s2 = "execution", what is the Levenshtein distance between them? Use the standard operations: insert, delete, substitute.

hard

A. 5

B. 6

C. 4

D. 7

Solution

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

   Compare characters and count minimal edits: substitutions and insertions/deletions.

2. Step 2: Calculate minimal edits manually

   Edits: i->e (substitution), n->x (substitution), t->c (substitution), insert u, substitute n->o, substitute n->n (no change), total 5 edits.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Distance("intention", "execution") = 5 [OK]

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing with Hamming distance