Edit Distance Problem Levenshtein in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

What is the output of the following C code that calculates the Levenshtein distance between two strings?

DSA C

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

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

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("kitten", "sitting"));
    return 0;
}

A 3

B 4

C 2

D 5

💡 Hint

Recall the minimum number of edits (insertions, deletions, substitutions) to convert 'kitten' to 'sitting'.

The Levenshtein distance between 'kitten' and 'sitting' is 3:

• Substitute 'k' with 's'
• Substitute 'e' with 'i'
• Insert 'g' at the end

🧠 Conceptual

intermediate

Understanding Levenshtein Distance Operations

Which of the following operations are considered in the Levenshtein distance calculation?

A Insertion, Swap, Transposition

B Insertion, Deletion, Substitution

C Substitution, Transposition, Swap

D Insertion, Deletion, Transposition

💡 Hint

Think about the basic edit operations allowed to transform one string into another.

Levenshtein distance counts the minimum number of insertions, deletions, and substitutions needed to change one string into another. Transposition is not included.

❓ Predict Output

advanced

Result of Levenshtein Distance with Empty String

What is the output of this C code snippet calculating the Levenshtein distance between an empty string and "abc"?

DSA C

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

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

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("", "abc"));
    return 0;
}

A 0

B 1

C 3

D 2

💡 Hint

Consider how many insertions are needed to convert an empty string to "abc".

To convert an empty string to "abc", we need 3 insertions, so the distance is 3.

🔧 Debug

advanced

Identify the Bug in Levenshtein Distance Code

What error will this C code produce when calculating the Levenshtein distance between "abc" and "yabd"?

DSA C

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

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

int levenshtein(const char *s1, const char *s2) {
    int len1 = strlen(s1);
    int len2 = strlen(s2);
    int *dp = malloc((len1 + 1) * (len2 + 1) * sizeof(int));
    for (int i = 0; i <= len1; i++) {
        for (int j = 0; j <= len2; j++) {
            if (i == 0) dp[j] = j;
            else if (j == 0) dp[i * (len2 + 1)] = i;
            else {
                int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
                int deletion = dp[(i - 1) * (len2 + 1) + j] + 1;
                int insertion = dp[i * (len2 + 1) + j - 1] + 1;
                int substitution = dp[(i - 1) * (len2 + 1) + j - 1] + cost;
                dp[i * (len2 + 1) + j] = min(deletion, insertion, substitution);
            }
        }
    }
    int result = dp[len1 * (len2 + 1) + len2];
    free(dp);
    return result;
}

int main() {
    printf("%d\n", levenshtein("abc", "yabd"));
    return 0;
}

A Infinite loop in nested for loops

B Correct output 2

C Compilation error due to missing header

D Segmentation fault due to incorrect dp indexing

💡 Hint

Check how dp array is accessed when i or j is zero.

The code incorrectly assigns dp[i * (len2 + 1)] = i when j == 0, but does not assign dp[i * (len2 + 1) + j] properly for all j when i == 0. This causes inconsistent dp initialization and may lead to segmentation fault.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

What is the time complexity of the classic dynamic programming algorithm to compute the Levenshtein distance between two strings of lengths m and n?

A O(m * n)

B O(m + n)

C O(2^(m+n))

D O(m^2 + n^2)

💡 Hint

Consider the size of the DP table and how many cells are computed.

The algorithm fills a table of size (m+1) x (n+1), computing each cell in constant time, resulting in O(m * n) time complexity.