Edit Distance Problem Levenshtein in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the 2D array for dynamic programming.

DSA Typescript

const dp: number[][] = Array(m + 1).fill(null).map(() => Array(n + 1).fill([1]));

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

A1

Bnull

C0

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing with 1 causes incorrect base cases.

Using null or -1 leads to runtime errors.

The DP table is initialized with 0 because the base case for edit distance starts with zero cost for empty strings.

2fill in blank

medium

Complete the code to fill the first row of the DP table representing insertions.

DSA Typescript

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

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

A+

B*

C-

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication or division instead of addition.

Using subtraction causes negative values.

We add 1 for each insertion to transform an empty string to the first j characters.

3fill in blank

hard

Fix the error in the condition to check if characters are equal.

DSA Typescript

if (word1[i - 1] [1] word2[j - 1]) {
  dp[i][j] = 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 '!=' reverses the logic causing wrong results.

Using '>=' or '<=' is incorrect for character comparison.

We check if characters are equal to avoid extra cost; use '==' for equality.

4fill in blank

hard

Fill both blanks to compute the minimum edit distance considering insert, delete, and replace.

DSA Typescript

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

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

A[i - 1][j - 1]

B[i][j - 1]

C[i - 1][j]

D[i][j]

Attempts:

3 left

💡 Hint

Common Mistakes

Mixing indices causes wrong minimum calculation.

Using dp[i][j] inside Math.min causes infinite recursion.

The three options are delete (dp[i-1][j]), insert (dp[i][j-1]), and replace (dp[i-1][j-1]). Here, blanks fill the replace case.

5fill in blank

hard

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

DSA Typescript

function levenshtein([1]: string, [2]: string): number {
  const m = [1].length;
  const n = [2].length;
  // ... DP initialization and computation ...
  return dp[m][n];
}

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

Aword1

Bword2

Cs1

Ds2

Attempts:

3 left

💡 Hint

Common Mistakes

Using different variable names causes reference errors.

Mismatching parameter names and length variables.

The function takes two strings named word1 and word2. We use word1.length and word2.length to get lengths.