Edit Distance Problem Levenshtein in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the base case for the first string length in the edit distance matrix.

DSA C

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

Drag options to blanks, or click blank then click option'

An

B0

Ci

Dm

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[i][0] to 0 instead of i

Using n instead of i

Using m instead of i

The first column of the matrix represents converting the first i characters of string1 to an empty string, which requires i deletions.

2fill in blank

medium

Complete the code to initialize the base case for the first string length in the edit distance matrix for the second string.

DSA C

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

Drag options to blanks, or click blank then click option'

Am

Bj

C0

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Setting dp[0][j] to 0 instead of j

Using m instead of j

Using n instead of j

The first row of the matrix represents converting an empty string to the first j characters of string2, which requires j insertions.

3fill in blank

hard

Fix the error in the condition that checks if characters at positions i-1 and j-1 are the same.

DSA C

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

Drag options to blanks, or click blank then click option'

A==

B=

C!=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '=' instead of '=='

Using '!=' which reverses the logic

Using '<' which is not correct for equality check

The condition must check if the characters are equal using '=='. Using '=' assigns a value and causes an error.

4fill in blank

hard

Fill both blanks to complete the min function calls to find the minimum edit distance operation cost.

DSA C

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

Drag options to blanks, or click blank then click option'

A-

B+

C*

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '*' instead of '-'

Using '/' which is invalid for indices

Using incorrect numbers for indices

The last term compares dp[i-1][j-1], so the blanks must be '-' and '1' respectively.

5fill in blank

hard

Fill all three blanks to complete the function signature and return statement for the Levenshtein distance function.

DSA C

[1] levenshtein_distance([2] s1, [3] s2) {
    int m = strlen(s1);
    int n = strlen(s2);
    int dp[m + 1][n + 1];
    // initialization and computation code here
    return dp[m][n];
}

Drag options to blanks, or click blank then click option'

Aint

Bchar*

Cconst char*

Dvoid

Attempts:

3 left

💡 Hint

Common Mistakes

Using void as return type

Using char* without const for input strings

Using int for input strings

The function returns an int distance and takes two constant character pointers as input strings.