Edit Distance Problem Levenshtein in DSA Typescript

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 until it matches the correct word.

word1: c a t
word2: c a r

Matrix:
    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Dry Run Walkthrough

Input: word1: "cat", word2: "car"

Goal: Calculate the minimum number of edits to change "cat" into "car"

Step 1: Initialize matrix with base cases for empty strings

    ''  c  a  r
''  0  1  2  3
c   1  .  .  .
a   2  .  .  .
t   3  .  .  .

Why: We need to know the cost of converting empty string to prefixes

Step 2: Compare 'c' and 'c', they match, copy diagonal value 0

    ''  c  a  r
''  0  1  2  3
c   1  0  .  .
a   2  .  .  .
t   3  .  .  .

Why: No edit needed if letters are the same

Step 3: Compare 'c' and 'a', letters differ, min(delete=2, insert=1, replace=1) = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  .
a   2  .  .  .
t   3  .  .  .

Why: Choose cheapest edit operation

Step 4: Compare 'c' and 'r', letters differ, min(delete=3, insert=2, replace=2) = 2

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  .  .  .
t   3  .  .  .

Why: Continue filling first row

Step 5: Compare 'a' and 'c', differ, min(delete=1, insert=3, replace=2) = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  .  .
t   3  .  .  .

Why: Fill second row considering edits

Step 6: Compare 'a' and 'a', match, copy diagonal 0

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  .
t   3  .  .  .

Why: No edit needed for matching letters

Step 7: Compare 'a' and 'r', differ, min(delete=3, insert=1, replace=2) = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  .  .  .

Why: Fill second row last column

Step 8: Compare 't' and 'c', differ, min(delete=2, insert=4, replace=3) = 2

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  .  .

Why: Fill third row first column

Step 9: Compare 't' and 'a', differ, min(delete=1, insert=3, replace=2) = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  .

Why: Fill third row second column

Step 10: Compare 't' and 'r', differ, min(delete=2, insert=2, replace=1) = 1

    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Why: Fill last cell with minimum edits

Result:

Final matrix:
    ''  c  a  r
''  0  1  2  3
c   1  0  1  2
a   2  1  0  1
t   3  2  1  1

Minimum edits = 1

Annotated Code

DSA Typescript

class EditDistance {
  static levenshtein(word1: string, word2: string): number {
    const m = word1.length;
    const n = word2.length;
    const dp: number[][] = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

    // Initialize base cases for empty strings
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    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 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
          );
        }
      }
    }
    return dp[m][n];
  }
}

// Driver code
const word1 = "cat";
const word2 = "car";
const result = EditDistance.levenshtein(word1, word2);
console.log(`Minimum edits to convert '${word1}' to '${word2}': ${result}`);

for (let i = 0; i <= m; i++) dp[i][0] = i;

initialize cost of deleting all letters from word1 to match empty word2

for (let j = 0; j <= n; j++) dp[0][j] = j;

initialize cost of inserting all letters to empty word1 to match word2

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

no edit needed if letters match, copy diagonal value

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

choose minimum cost among delete, insert, replace operations

Output

Minimum edits to convert 'cat' to 'car': 1

Complexity Analysis

Time: O(m*n) because we fill a matrix 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 causing exponential time, DP avoids this by storing results

Edge Cases

One or both words empty

Returns length of the other word as all insertions or deletions

DSA Typescript

for (let i = 0; i <= m; i++) dp[i][0] = i;

Words are identical

Returns 0 as no edits needed

DSA Typescript

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

Words differ completely

Returns length of longer word as all replacements

DSA Typescript

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

When to Use This Pattern

When asked to find minimum changes to convert one string to another, use the Levenshtein distance dynamic programming pattern to efficiently compute edits.

Common Mistakes

Mistake: Forgetting to initialize the first row and column of the matrix
Fix: Add loops to fill dp[i][0] and dp[0][j] with incremental costs for empty string conversions

Mistake: Mixing up indices when accessing characters in strings
Fix: Use i-1 and j-1 to access characters because dp matrix includes empty prefix at index 0

Summary

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

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

The key insight is building a matrix that stores solutions for smaller parts to solve the whole problem efficiently.

Practice

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

easy

A. The maximum length of common substring between two strings

B. The number of characters that are the same in both strings

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

D. The total length of both strings combined

Solution

1. Step 1: Understand the definition of Levenshtein distance

   It counts the minimum edits (insertions, deletions, substitutions) needed to convert one string into another.

2. Step 2: Compare with other options

   Options A, C, and D describe different string metrics, not edit distance.

3. Final Answer:

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

4. Quick Check:

   Edit distance = minimum edits [OK]

Hint: Edit distance counts minimal edits to match strings [OK]

Common Mistakes:

• Confusing edit distance with longest common substring
• Thinking it counts only substitutions, not insertions/deletions
• Assuming it measures similarity score instead of edit count

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

easy

A. function levenshtein(s1: string, s2: string): number

B. function levenshtein(s1: number, s2: number): string

C. function levenshtein(s1: string[], s2: string[]): boolean

D. function levenshtein(s1: any, s2: any): void

Solution

1. Step 1: Identify correct parameter and return types

   Levenshtein distance takes two strings and returns a number representing the edit distance.

2. Step 2: Check each option's signature

   function levenshtein(s1: string, s2: string): number matches the expected input and output types. Others mismatch types or return void.

3. Final Answer:

   function levenshtein(s1: string, s2: string): number -> Option A

4. Quick Check:

   Input strings, output number [OK]

Hint: Input strings, output number for edit distance [OK]

Common Mistakes:

• Using wrong parameter types like arrays or numbers
• Returning wrong types like boolean or void
• Using any type without specifying string inputs

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

function levenshtein(s1: string, s2: string): number {
  const dp: number[][] = [];
  for (let i = 0; i <= s1.length; i++) {
    dp[i] = [i];
  }
  for (let j = 0; j <= s2.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= s1.length; i++) {
    for (let j = 1; j <= s2.length; 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[s1.length][s2.length];
}

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

medium

A. 3

B. 4

C. 5

D. 6

Solution

1. Step 1: Initialize DP table for 'kitten' and 'sitting'

   DP table rows = 7, columns = 8. Base cases set for empty prefixes.

2. Step 2: Fill DP table comparing characters and calculating minimum edits

   Calculations show minimum edits needed to convert 'kitten' to 'sitting' is 3 (substitute 'k'->'s', 'e'->'i', insert 'g').

3. Final Answer:

   3 -> Option A

4. Quick Check:

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

Hint: Trace DP table for small strings to find edit count [OK]

Common Mistakes:

• Counting only substitutions, ignoring insertions/deletions
• Off-by-one errors in indexing strings
• Misreading the DP initialization steps

4. Identify the bug in this TypeScript implementation of Levenshtein distance:

function levenshtein(s1: string, s2: string): number {
  const dp: number[][] = [];
  for (let i = 0; i < s1.length; i++) {
    dp[i] = [i];
  }
  for (let j = 0; j < s2.length; j++) {
    dp[0][j] = j;
  }
  for (let i = 1; i <= s1.length; i++) {
    for (let j = 1; j <= s2.length; 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], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
      }
    }
  }
  return dp[s1.length][s2.length];
}

medium

A. The function should return dp[0][0] instead of dp[s1.length][s2.length]

B. The dp array should be initialized with zeros instead of indices

C. The comparison should be s1[i] === s2[j], not s1[i - 1] === s2[j - 1]

D. The loops initializing dp should run up to <= length, not < length

Solution

1. Step 1: Check dp initialization loops

   Loops run from 0 to less than length, but dp needs size length+1 to include empty prefix cases.

2. Step 2: Correct loop ranges to include dp[s1.length] and dp[s2.length]

   Change loops to run up to <= length to properly initialize dp edges.

3. Final Answer:

   The loops initializing dp should run up to <= length, not < length -> Option D

4. Quick Check:

   DP size must cover full string lengths [OK]

Hint: Initialize DP arrays with length+1 for empty string cases [OK]

Common Mistakes:

• Using < length instead of <= length in loops
• Incorrect string index comparisons causing off-by-one errors
• Returning wrong dp cell ignoring full string lengths

5. Given two strings s1 = 'intention' and s2 = 'execution', what is the minimum edit distance using Levenshtein algorithm? Also, explain why this distance is correct.

hard

A. 6

B. 5

C. 4

D. 7

Solution

1. Step 1: Analyze transformations from 'intention' to 'execution'

   Operations include substituting 'i'->'e', 'n'->'x', deleting 't', substituting 'n'->'c', substituting 't'->'u'. Counting these gives 5 edits.

2. Step 2: Confirm minimal edits with DP approach

   DP table confirms minimum edits needed is 5, as fewer edits cannot convert all differing characters.

3. Final Answer:

   5 -> Option B

4. Quick Check:

   Minimum edits = 5 for 'intention' to 'execution' [OK]

Hint: Count substitutions, insertions, deletions carefully [OK]

Common Mistakes:

• Underestimating edits by ignoring deletions
• Counting only substitutions
• Misaligning characters causing wrong counts