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 correcting 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 change as one step.

word1: c a t
word2: c a r

We compare letters one by one and decide if we need to change, add, or remove letters to match.

Dry Run Walkthrough

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

Goal: Find the minimum steps to change "cat" into "car"

Step 1: Compare first letters 'c' and 'c', they match, no change needed

cost matrix:
  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2
3 3

Why: Matching letters cost 0, so we keep the cost from previous step

Step 2: Compare second letters 'a' and 'a', they match, no change needed

cost matrix:
  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2 1 2
3 3

Why: Matching letters cost 0, so cost stays same as previous

Step 3: Compare third letters 't' and 'r', they differ, consider replace, insert, delete

cost matrix:
  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2 1 2 2
3 3 2 2 1

Why: Replace 't' with 'r' costs 1, which is minimum among insert/delete/replace

Result:

Minimum edit distance = 1
Final cost matrix:
  0 1 2 3
0 0 1 2 3
1 1 0 1 2
2 2 1 2 2
3 3 2 2 1

Annotated Code

DSA C

#include <stdio.h>
#include <string.h>

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int editDistance(char *word1, char *word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i; // cost of deleting all letters from word1
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j; // cost of inserting all letters to word1
    }

    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; // letters match, no cost
            } else {
                dp[i][j] = 1 + min(
                    dp[i - 1][j],    // delete
                    dp[i][j - 1],    // insert
                    dp[i - 1][j - 1] // replace
                );
            }
        }
    }
    return dp[len1][len2];
}

int main() {
    char word1[] = "cat";
    char word2[] = "car";
    int dist = editDistance(word1, word2);
    printf("Minimum edit distance = %d\n", dist);
    return 0;
}

dp[i][0] = i; // cost of deleting all letters from word1

initialize first column: cost to delete letters to match empty string

dp[0][j] = j; // cost of inserting all letters to word1

initialize first row: cost to insert letters to match word2

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

if letters match, carry cost; else choose min cost among delete, insert, replace plus one

Output

Minimum edit distance = 1

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n where m and n are the lengths of the two words

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

vs Alternative: Naive recursive approach has exponential time due to repeated subproblems; dynamic programming reduces it to polynomial time by storing results

Edge Cases

One or both words are empty strings

The edit distance equals the length of the non-empty word (all insertions or deletions)

DSA C

dp[i][0] = i; // cost of deleting all letters from word1

Both words are identical

Edit distance is zero since no changes are needed

DSA C

if (word1[i - 1] == word2[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1];

Words differ completely

Algorithm counts minimum edits by considering all operations at each step

DSA C

dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);

When to Use This Pattern

When you need to find how similar two strings are by counting changes, use the Edit Distance pattern because it systematically counts minimal edits.

Common Mistakes

Mistake: Not initializing the first row and column of the dp table correctly
Fix: Initialize dp[i][0] = i and dp[0][j] = j to represent base cases of empty strings

Mistake: Confusing indices when accessing characters of the strings
Fix: Use i-1 and j-1 to access characters because dp indices start from 1 for convenience

Mistake: Forgetting to add 1 when choosing among insert, delete, replace operations
Fix: Add 1 to the minimum of the three operations to count the current edit

Summary

Calculates the minimum number of insertions, deletions, or replacements to convert one word into another.

Use when you want to measure how different two strings are or find the minimal edits to transform one string into another.

The key insight is to build a table of solutions for smaller parts and use them to solve the bigger problem efficiently.

Practice

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

easy

A. The minimum number of insertions, deletions, or substitutions to convert one string into another

B. The number of matching characters in the same positions

C. The length difference between two strings

D. The maximum number of characters that differ between two strings

Solution

1. Step 1: Understand the definition of Edit Distance

   Edit Distance counts the smallest number of changes needed to turn one string into another.

2. Step 2: Identify allowed operations

   These operations include insertion, deletion, and substitution of characters.

3. Final Answer:

   The minimum number of insertions, deletions, or substitutions to convert one string into another -> Option A

4. Quick Check:

   Edit Distance = minimum edits needed [OK]

Hint: Think of edits needed to match strings exactly [OK]

Common Mistakes:

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

2. Which of the following is the correct way to initialize the first row of the DP table for Levenshtein distance in C?

easy

A. for (int j = 0; j <= n; j++) dp[0][j] = j;

B. for (int i = 0; i <= m; i++) dp[i][0] = i;

C. for (int j = 1; j <= n; j++) dp[0][j] = 0;

D. for (int i = 1; i <= m; i++) dp[0][i] = i;

Solution

1. Step 1: Identify the DP table dimensions

   The DP table has dimensions (m+1) x (n+1), where m and n are string lengths.

2. Step 2: Initialize first row correctly

   The first row dp[0][j] represents converting empty string to prefix of second string, so dp[0][j] = j.

3. Final Answer:

   for (int j = 0; j <= n; j++) dp[0][j] = j; -> Option A

4. Quick Check:

   First row = 0 to n [OK]

Hint: First row = indices of second string length [OK]

Common Mistakes:

• Mixing row and column indices
• Starting loop from 1 instead of 0
• Initializing first column instead of first row

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

int min(int a, int b, int c) {
    int m = a < b ? a : b;
    return m < c ? m : c;
}

int levenshtein(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m+1][n+1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int cost = (s[i-1] == t[j-1]) ? 0 : 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];
}

printf("%d", levenshtein("kitten", "sitting"));

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the strings and operations

   "kitten" to "sitting" requires substitutions and insertions: k->s, e->i, add g.

2. Step 2: Calculate minimum edits

   Minimum edits are 3 substitutions and 1 insertion = 4 total edits.

3. Final Answer:

   4 -> Option B

4. Quick Check:

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

Hint: Recall classic example: kitten -> sitting = 4 edits [OK]

Common Mistakes:

• Counting only substitutions, missing insertions
• Confusing character positions
• Off-by-one errors in indexing

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

int levenshtein(char *s, char *t) {
    int m = strlen(s), n = strlen(t);
    int dp[m][n];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int cost = (s[i-1] == t[j-1]) ? 0 : 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];
}

medium

A. Loops should start from 0, not 1

B. The cost calculation is incorrect

C. dp array size should be (m+1) x (n+1), not m x n

D. Return statement should be dp[m-1][n-1]

Solution

1. Step 1: Check dp array declaration

   dp is declared as dp[m][n], but indices go up to m and n inclusive, so size is insufficient.

2. Step 2: Understand indexing needs

   We need dp of size (m+1) x (n+1) to store base cases and full computation.

3. Final Answer:

   dp array size should be (m+1) x (n+1), not m x n -> Option C

4. Quick Check:

   dp size = (m+1)*(n+1) [OK]

Hint: DP table size must cover all indices including zero [OK]

Common Mistakes:

• Declaring dp too small causing out-of-bounds errors
• Misunderstanding loop ranges
• Incorrect return index

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

hard

A. 7

B. 8

C. 5

D. 6

Solution

1. Step 1: Analyze string lengths and differences

   "intention" and "execution" differ in several characters and positions.

2. Step 2: Calculate minimum edits stepwise

   Edits include substitutions (i->e, n->x, t->e, e->c, n->u, etc.) totaling 6 changes.

3. Final Answer:

   6 -> Option D

4. Quick Check:

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

Hint: Count substitutions and insertions carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing similar characters as matches