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.