Edit Distance Problem Levenshtein in DSA Javascript

Mental Model

Find the smallest number of changes needed to turn one word into another by adding, removing, or changing letters.

Analogy: Imagine fixing a typo in a word by either adding missing letters, deleting extra ones, or changing wrong letters to the right ones, counting each fix as one step.

word1: c a t
word2: c a r

We want to see how many steps to change 'cat' -> 'car'.

Dry Run Walkthrough

Input: word1: 'cat', word2: 'car'

Goal: Find the minimum edits to change 'cat' into 'car'.

Step 1: Compare last letters 't' and 'r', they differ, so consider replace operation.

distance matrix after first row and column filled:
  '' c a t
'' 0 1 2 3
c  1 0 1 2

Why: We start by setting base cases: empty string to prefixes costs equal to prefix length.

Step 2: Compare 'a' and 'a', they match, so no extra cost here.

distance matrix updated:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1

Why: Matching letters mean no new edit needed, so cost stays the same as previous.

Step 3: Compare 't' and 'r', they differ, so consider replace operation with cost 1.

distance matrix final:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 1

Why: We pick minimum among insert, delete, replace; here replace cost is 1, so total edits is 1.

Result:

Minimum edit distance matrix:
  '' c a t
'' 0 1 2 3
c  1 0 1 2
a  2 1 0 1
r  3 2 1 1

Answer: 1 (change 't' to 'r')

Annotated Code

DSA Javascript

class EditDistance {
  static levenshtein(word1, word2) {
    const m = word1.length;
    const n = word2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    for (let i = 0; i <= m; i++) {
      dp[i][0] = i; // cost of deleting all letters from word1
    }
    for (let j = 0; j <= n; j++) {
      dp[0][j] = j; // cost of inserting all letters to word1
    }

    for (let i = 1; i <= m; i++) {
      for (let j = 1; j <= n; j++) {
        if (word1[i - 1] === word2[j - 1]) {
          dp[i][j] = dp[i - 1][j - 1]; // letters match, no new edit
        } else {
          dp[i][j] = Math.min(
            dp[i - 1][j] + 1,    // delete letter from word1
            dp[i][j - 1] + 1,    // insert letter to word1
            dp[i - 1][j - 1] + 1 // replace letter
          );
        }
      }
    }
    return dp[m][n];
  }
}

// Driver code
const word1 = 'cat';
const word2 = 'car';
const distance = EditDistance.levenshtein(word1, word2);
console.log(`Minimum edit distance between '${word1}' and '${word2}' is: ${distance}`);

dp[i][0] = i; // cost of deleting all letters from word1

initialize base case for empty second word

dp[0][j] = j; // cost of inserting all letters to word1

initialize base case for empty first word

if (word1[i - 1] === word2[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; // letters match, no new edit } else { dp[i][j] = Math.min( dp[i - 1][j] + 1, // delete dp[i][j - 1] + 1, // insert dp[i - 1][j - 1] + 1 // replace ); }

choose minimum edit operation cost for current letters

Output

Minimum edit distance between 'cat' and 'car' is: 1

Complexity Analysis

Time: O(m*n) because we fill a table of size m by n once

Space: O(m*n) because we store edit distances for all substring pairs

vs Alternative: Naive recursive approach repeats calculations and is exponential, DP avoids repeated work by storing results

Edge Cases

One or both words empty

Distance equals length of the other word (all insertions or deletions)

DSA Javascript

dp[i][0] = i; // cost of deleting all letters from word1

Both words are the same

Distance is zero because no edits needed

DSA Javascript

if (word1[i - 1] === word2[j - 1]) {
  dp[i][j] = dp[i - 1][j - 1];

Words with repeated letters

Algorithm correctly counts edits considering each letter position

DSA Javascript

dp[i][j] = Math.min(...);

When to Use This Pattern

When asked to find the minimum number of changes to convert one string into another, use the Levenshtein edit distance dynamic programming pattern.

Common Mistakes

Mistake: Not initializing the first row and column of the DP table
Fix: Explicitly set dp[i][0] = i and dp[0][j] = j to handle empty string cases

Mistake: Comparing wrong characters due to off-by-one errors
Fix: Use word1[i-1] and word2[j-1] when indexing inside loops starting from 1

Summary

Calculates the minimum number of insertions, deletions, and replacements to convert one word into another.

Use when you need to measure how different two strings are or fix typos with minimal changes.

The key is building a table that stores solutions to smaller problems to solve the big problem efficiently.

Practice

1. What does the Levenshtein distance between two strings measure?

easy

A. The length difference between the two strings

B. The number of matching characters in the same positions

C. The minimum number of single-character edits needed to change one string into the other

D. The number of vowels in both strings combined

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It measures how many single-character edits (insertions, deletions, or substitutions) are needed to convert one string into another.

2. Step 2: Compare with other options

   Options B, C, and D do not describe edit distance but other unrelated string properties.

3. Final Answer:

   The minimum number of single-character edits needed to change one string into the other -> Option C

4. Quick Check:

   Levenshtein distance = minimum edits [OK]

Hint: Think of edits needed to transform one word into another [OK]

Common Mistakes:

• Confusing edit distance with matching characters count
• Thinking it measures length difference only
• Assuming it counts only substitutions

2. Which of the following JavaScript function signatures correctly represents a function to compute Levenshtein distance between two strings s1 and s2?

easy

A. function levenshtein(s1, s2) { /* code */ }

B. function levenshtein(s1, s2, s3) { /* code */ }

C. function levenshtein() { /* code */ }

D. function levenshtein(s1) { /* code */ }

Solution

1. Step 1: Identify required parameters for Levenshtein function

   The function needs exactly two strings to compare, so it should accept two parameters.

2. Step 2: Check options for correct parameter count

   function levenshtein(s1, s2) { /* code */ } has two parameters (s1, s2), which is correct. Options A, B, and C have incorrect parameter counts.

3. Final Answer:

   function levenshtein(s1, s2) { /* code */ } -> Option A

4. Quick Check:

   Two strings needed as input [OK]

Hint: Levenshtein compares two strings, so function needs two parameters [OK]

Common Mistakes:

• Using wrong number of parameters
• Omitting parameters entirely
• Adding unnecessary extra parameters

3. What is the output of the following JavaScript code snippet?

function min(a, b, c) {
  return Math.min(a, b, c);
}

function levenshtein(s1, s2) {
  const len1 = s1.length;
  const len2 = s2.length;
  const dp = Array(len1 + 1).fill(null).map(() => Array(len2 + 1).fill(0));

  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1];
      } else {
        dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
      }
    }
  }
  return dp[len1][len2];
}

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

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Understand the Levenshtein distance calculation for 'kitten' and 'sitting'

   Transform 'kitten' to 'sitting' requires 3 substitutions and 1 insertion: k->s, i->i (same), t->t (same), t->t (same), e->i, n->n (same), plus insert 'g'. Total edits = 3.

2. Step 2: Trace the code logic

   The code correctly implements the dynamic programming approach to calculate the minimum edits, returning 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Levenshtein('kitten', 'sitting') = 3 [OK]

Hint: Count edits: substitutions + insertions + deletions [OK]

Common Mistakes:

• Counting only substitutions
• Ignoring insertions or deletions
• Misindexing string characters

4. Identify the bug in the following Levenshtein distance function and select the fix:

function levenshtein(s1, s2) {
  const len1 = s1.length;
  const len2 = s2.length;
  const dp = Array(len1).fill(null).map(() => Array(len2).fill(0));

  for (let i = 0; i <= len1; i++) dp[i][0] = i;
  for (let j = 0; j <= len2; j++) dp[0][j] = j;

  for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
      if (s1[i - 1] === s2[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[len1][len2];
}

medium

A. Change loops to run from 0 to len1-1 and len2-1

B. Replace Math.min with Math.max in dp calculation

C. Remove the initialization loops for dp first row and column

D. Change dp array initialization to size (len1+1) x (len2+1)

Solution

1. Step 1: Analyze dp array initialization

   The dp array is initialized with size len1 x len2, but the loops access indices up to len1 and len2, causing out-of-bounds errors.

2. Step 2: Fix dp size to (len1+1) x (len2+1)

   Allocating dp with one extra row and column prevents index errors and allows proper initialization of base cases.

3. Final Answer:

   Change dp array initialization to size (len1+1) x (len2+1) -> Option D

4. Quick Check:

   dp size must match loop bounds [OK]

Hint: dp size must be string length + 1 for indexing [OK]

Common Mistakes:

• Not allocating dp with extra row/column
• Using wrong loop ranges causing errors
• Replacing min with max breaks logic

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the Levenshtein distance between them? Use the concept of minimum edits (insertions, deletions, substitutions) to find the answer.

hard

A. 4

B. 6

C. 5

D. 7

Solution

1. Step 1: Analyze differences between 'intention' and 'execution'

   Transform 'intention' to 'execution' involves substitutions and insertions: i->e, n->x, t->c, e->u, n->t, plus insert 'o'. Total edits count to 6.

2. Step 2: Count minimum edits carefully

   Counting substitutions and insertions needed gives 6 as the minimum number of edits.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Minimum edits between 'intention' and 'execution' = 6 [OK]

Hint: Count each letter change and insertion carefully [OK]

Common Mistakes:

• Underestimating substitutions needed
• Ignoring insertions or deletions
• Confusing with string length difference