Edit Distance Problem Levenshtein in DSA Javascript - Build from Scratch

Edit Distance Problem Levenshtein

📖 Scenario: You are building a simple spell checker that measures how different two words are. This difference is called the Levenshtein distance, which counts how many single-letter changes (insertions, deletions, or substitutions) are needed to change one word into another.Understanding this helps computers suggest correct spellings or find similar words.

🎯 Goal: Build a program that calculates the Levenshtein distance between two given words using a step-by-step approach.

📋 What You'll Learn

Create a 2D array to hold distances between prefixes of the two words

Initialize the first row and first column of the 2D array

Fill the 2D array using the Levenshtein distance rules

Print the final Levenshtein distance value

💡 Why This Matters

🌍 Real World

Spell checkers, auto-correct features, DNA sequence analysis, and plagiarism detection use Levenshtein distance to find how similar two strings are.

💼 Career

Understanding string similarity algorithms is important for software engineers working on text processing, search engines, and natural language processing.

1

Create the input words and initialize the 2D array

Create two string variables called word1 and word2 with values "kitten" and "sitting" respectively. Then create a 2D array called distance with dimensions word1.length + 1 by word2.length + 1, filled with zeros.

DSA Javascript

// Your code here

Hint

Use Array(length).fill(value) and map to create a 2D array.

2

Initialize the first row and first column of the 2D array

Use two for loops to fill the first row of distance with values from 0 to word2.length and the first column with values from 0 to word1.length.

DSA Javascript

const word1 = "kitten";
const word2 = "sitting";

const distance = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));

// Your code here

Hint

Fill the edges of the 2D array to represent converting empty strings to prefixes.

3

Fill the 2D array using Levenshtein distance rules

Use nested for loops with variables i and j starting from 1 to fill the distance array. For each position, check if word1[i - 1] equals word2[j - 1]. If equal, set distance[i][j] to distance[i - 1][j - 1]. Otherwise, set it to 1 plus the minimum of distance[i - 1][j], distance[i][j - 1], and distance[i - 1][j - 1].

DSA Javascript

const word1 = "kitten";
const word2 = "sitting";

const distance = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));

for (let i = 0; i <= word1.length; i++) {
    distance[i][0] = i;
}
for (let j = 0; j <= word2.length; j++) {
    distance[0][j] = j;
}

// Your code here

Hint

Use nested loops and check characters at i - 1 and j - 1 positions.

4

Print the final Levenshtein distance

Print the value at distance[word1.length][word2.length] using console.log.

DSA Javascript

const word1 = "kitten";
const word2 = "sitting";

const distance = Array(word1.length + 1).fill(null).map(() => Array(word2.length + 1).fill(0));

for (let i = 0; i <= word1.length; i++) {
    distance[i][0] = i;
}
for (let j = 0; j <= word2.length; j++) {
    distance[0][j] = j;
}

for (let i = 1; i <= word1.length; i++) {
    for (let j = 1; j <= word2.length; j++) {
        if (word1[i - 1] === word2[j - 1]) {
            distance[i][j] = distance[i - 1][j - 1];
        } else {
            distance[i][j] = 1 + Math.min(distance[i - 1][j], distance[i][j - 1], distance[i - 1][j - 1]);
        }
    }
}

// Your code here

Hint

The final answer is the value in the bottom-right corner of the 2D array.

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