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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Levenshtein Distance Calculation

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

DSA Typescript

function levenshtein(a: string, b: string): number {
  const dp: number[][] = [];
  for (let i = 0; i <= a.length; i++) {
    dp[i] = [];
    dp[i][0] = i;
  }
  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(levenshtein("kitten", "sitting"));

A 3

B 4

C 2

D 5

💡 Hint

Think about 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 Matrix Initialization

In the Levenshtein distance algorithm, why do we initialize the first row and first column of the matrix with incremental values?

A They are placeholders and do not affect the final result.

B They store the maximum possible edit distance between the two strings.

C They represent the cost of converting an empty string to the other string by insertions or deletions.

D They represent the number of substitutions needed to match the strings.

💡 Hint

Think about how many edits it takes to get from an empty string to a string of length n.

The first row and column represent the cost of converting an empty string to a substring by only insertions or deletions, so they are initialized incrementally.

🔧 Debug

advanced

Identify the Error in Levenshtein Distance Implementation

What error will the following TypeScript code produce when calculating the Levenshtein distance?

DSA Typescript

function levenshtein(a: string, b: string): number {
  const dp: number[][] = [];
  for (let i = 0; i < a.length; i++) {
    dp[i] = [];
    dp[i][0] = i;
  }
  for (let j = 0; j <= b.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[a.length][b.length];
}

console.log(levenshtein("abc", "yabd"));

A TypeError: Cannot set property '0' of undefined

B SyntaxError due to missing semicolon

C Returns incorrect distance value 2

D Returns correct distance value 3

💡 Hint

Check how the dp array is initialized for the first row and column.

The loop initializing dp for rows uses i < a.length, so dp[a.length] is undefined when accessed later, causing a TypeError when setting dp[a.length][j].

🚀 Application

advanced

Minimum Edit Operations to Convert Strings

Given the strings 'intention' and 'execution', what is the minimum number of edit operations (insertions, deletions, substitutions) needed to convert one into the other?

A 4

B 6

C 7

D 5

💡 Hint

Try to count the edits step-by-step or use the Levenshtein distance logic.

The Levenshtein distance between 'intention' and 'execution' is 5, representing the minimum edits needed.

🧠 Conceptual

expert

Time Complexity of Levenshtein Distance Algorithm

What is the time complexity of the classic dynamic programming solution for the Levenshtein distance between two strings of lengths m and n?

A O(2^(m + n))

B O(m * n)

C O(m^2 + n^2)

D O(m + n)

💡 Hint

Consider the size of the matrix filled during the algorithm.

The algorithm fills a matrix of size m by n, performing constant work per cell, resulting in O(m * n) time complexity.