Edit Distance Problem Levenshtein in DSA C - Build from Scratch

Edit Distance Problem Levenshtein

📖 Scenario: You are building a simple spell checker that measures how different two words are by counting the minimum number of edits needed to change one word into the other. Edits can be inserting, deleting, or replacing a letter.This difference is called the Levenshtein distance.

🎯 Goal: Calculate the Levenshtein distance between two given words using dynamic programming in C.

📋 What You'll Learn

Create two strings word1 and word2 with exact values

Create an integer variable len1 for the length of word1 and len2 for the length of word2

Create a 2D integer array dp of size (len1+1) x (len2+1) to store intermediate results

Fill the dp array using the Levenshtein distance logic

Print the final edit distance stored in dp[len1][len2]

💡 Why This Matters

🌍 Real World

Spell checkers, auto-correct features, DNA sequence analysis, and natural language processing use edit distance to find how similar two strings are.

💼 Career

Understanding dynamic programming and string algorithms like Levenshtein distance is important for software engineers working on text processing, search engines, and bioinformatics.

1

DATA SETUP: Create the input words

Create two strings called word1 with value "kitten" and word2 with value "sitting".

DSA C

# Your code here

Hint

Use char word1[] = "kitten"; and char word2[] = "sitting"; to create the words.

2

CONFIGURATION: Calculate lengths and declare dp array

Add two integer variables len1 and len2 to store the lengths of word1 and word2 using strlen. Then declare a 2D integer array dp of size len1 + 1 by len2 + 1.

DSA C

#include 
#include 

int main() {
    char word1[] = "kitten";
    char word2[] = "sitting";
    // Your code here
    return 0;
}

Hint

Use strlen(word1) and strlen(word2) to get lengths. Declare dp as int dp[len1 + 1][len2 + 1];.

3

CORE LOGIC: Fill dp array with Levenshtein distance values

Use two nested for loops with variables i from 0 to len1 and j from 0 to len2. Inside, fill dp[i][j] as follows: if i == 0, set dp[i][j] = j; else if j == 0, set dp[i][j] = i; else if word1[i-1] == word2[j-1], set dp[i][j] = dp[i-1][j-1]; otherwise, set dp[i][j] to 1 plus the minimum of dp[i-1][j], dp[i][j-1], and dp[i-1][j-1].

DSA C

#include 
#include 

int main() {
    char word1[] = "kitten";
    char word2[] = "sitting";
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1 + 1][len2 + 1];
    // Your code here
    return 0;
}

Hint

Use nested loops and conditions to fill dp. Use a helper min function to find the smallest of three values.

4

OUTPUT: Print the final Levenshtein distance

Print the integer value stored in dp[len1][len2] using printf with the format "%d\n".

DSA C

#include 
#include 

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

int main() {
    char word1[] = "kitten";
    char word2[] = "sitting";
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[len1 + 1][len2 + 1];

    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) {
                dp[i][j] = j;
            } else if (j == 0) {
                dp[i][j] = i;
            } else if (word1[i - 1] == word2[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]);
            }
        }
    }

    // Your code here
    return 0;
}

Hint

Use printf("%d\n", dp[len1][len2]); to print the final edit distance.

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