Edit Distance Problem Levenshtein in DSA Typescript - Deep Dive

Overview - Edit Distance Problem Levenshtein

What is it?

The Edit Distance Problem, also known as Levenshtein distance, measures how many changes are needed to turn one word into another. These changes can be adding, removing, or changing a single letter. It helps computers understand how similar two words are. This is useful in spell checking, DNA analysis, and more.

Why it matters

Without this concept, computers would struggle to compare words or strings that are slightly different. For example, spell checkers wouldn't know which word you meant if you typed it wrong. It solves the problem of measuring similarity in a way that matches human intuition about small mistakes or changes.

Where it fits

Before learning this, you should understand basic strings and arrays. After this, you can explore dynamic programming techniques and other string algorithms like Longest Common Subsequence or Damerau-Levenshtein distance.

Mental Model

Core Idea

Edit distance is the smallest number of single-letter changes needed to turn one word into another.

Think of it like...

Imagine you have two sentences written on paper, and you want to make them the same by erasing, writing, or changing one letter at a time. The edit distance counts the fewest steps needed to do this.

  Word1: s i t t i n g
  Word2: k i t t e n

  Steps:
  s -> k (substitution)
  i -> i (no change)
  t -> t (no change)
  t -> t (no change)
  i -> e (substitution)
  n -> n (no change)
  g -> (deletion)

  Total edits = 3

Build-Up - 7 Steps

1

Foundation

Understanding Basic String Operations

Concept: Learn what it means to insert, delete, or substitute a character in a string.

Insertion means adding a letter anywhere in the word. Deletion means removing a letter. Substitution means changing one letter to another. For example, changing 'cat' to 'bat' is one substitution. Changing 'cat' to 'cats' is one insertion.

Result

You can now identify the three basic operations that change one string into another.

Knowing these operations is essential because edit distance counts how many of these changes are needed.

2

Foundation

What is Edit Distance?

Concept: Edit distance counts the minimum number of insertions, deletions, and substitutions to convert one string into another.

For example, to change 'kitten' to 'sitting': - Substitute 'k' with 's' - Substitute 'e' with 'i' - Insert 'g' at the end Total edits = 3 This number is the edit distance.

Result

You understand that edit distance is a number representing how different two words are.

This number helps computers compare words even if they are not exactly the same.

3

Intermediate

Dynamic Programming Table Setup

🤔Before reading on: do you think we can solve edit distance by checking all possible changes directly? Commit to yes or no.

Concept: Use a table to store results of smaller problems to avoid repeating work.

Create a 2D table where rows represent letters of the first word and columns represent letters of the second word. Each cell shows the edit distance between prefixes of the two words. Fill the table starting from empty strings up to full words.

Result

You have a structured way to calculate edit distance efficiently.

Using a table avoids recalculating the same subproblems, making the solution much faster.

4

Intermediate

Filling the Table with Recurrence

🤔Before reading on: do you think the cost to change prefixes depends only on the last letters or the whole strings? Commit to your answer.

Concept: Each cell depends on three possible previous cells representing insertion, deletion, or substitution.

To fill cell[i][j]: - If letters match, cost = cell[i-1][j-1] - Else cost = 1 + min( cell[i-1][j] (deletion), cell[i][j-1] (insertion), cell[i-1][j-1] (substitution)) This builds the solution from smaller to bigger prefixes.

Result

You can compute the edit distance by filling the table step-by-step.

Understanding this recurrence is key to implementing the algorithm correctly.

5

Intermediate

Implementing Levenshtein Distance in TypeScript

Concept: Translate the dynamic programming logic into runnable TypeScript code.

function levenshtein(a: string, b: string): number { const dp: number[][] = Array(a.length + 1).fill(null).map(() => Array(b.length + 1).fill(0)); for (let i = 0; i <= a.length; 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] = 1 + Math.min( dp[i - 1][j], // deletion dp[i][j - 1], // insertion dp[i - 1][j - 1] // substitution ); } } } return dp[a.length][b.length]; } // Example: console.log(levenshtein('kitten', 'sitting')); // Output: 3

Result

The function returns 3 for 'kitten' to 'sitting', matching the expected edit distance.

Seeing the code helps connect the theory to practical implementation.

6

Advanced

Optimizing Space Complexity

🤔Before reading on: do you think we need to keep the entire table in memory? Commit to yes or no.

Concept: We can reduce memory use by storing only the current and previous rows of the table.

Since each dp[i][j] depends only on dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], we only need two rows at a time. This reduces space from O(m*n) to O(min(m,n)).

Result

The algorithm uses much less memory while producing the same result.

Knowing this optimization is important for large strings or memory-limited environments.

7

Expert

Handling Transpositions with Damerau-Levenshtein

🤔Before reading on: do you think swapping two adjacent letters counts as two edits or one? Commit to your answer.

Concept: Damerau-Levenshtein distance extends Levenshtein by counting swapping two adjacent letters as one edit.

This is useful for common typos like 'form' vs 'from'. The algorithm adds a check for transpositions when filling the table, allowing one swap operation.

Result

The distance can be smaller than Levenshtein when transpositions occur, better matching human errors.

Understanding this extension helps in applications like spell checkers where letter swaps are common.

Under the Hood

The algorithm builds a matrix where each cell represents the minimum edits to convert prefixes of the two strings. It uses previous results to avoid repeated work. The process is bottom-up dynamic programming, filling the matrix row by row.

Why designed this way?

This design avoids exponential time from trying all edit sequences by breaking the problem into smaller overlapping subproblems. Early solutions used recursion with heavy repetition; dynamic programming made it efficient and practical.

  +---+---+---+---+---+
  |   |   | b | a | t |
  +---+---+---+---+---+
  |   | 0 | 1 | 2 | 3 |
  +---+---+---+---+---+
  | c | 1 | 1 | 2 | 3 |
  +---+---+---+---+---+
  | a | 2 | 2 | 1 | 2 |
  +---+---+---+---+---+
  | t | 3 | 3 | 2 | 1 |
  +---+---+---+---+---+

Myth Busters - 4 Common Misconceptions

Quick: Does edit distance count swapping two letters as one edit? Commit yes or no.

Common Belief: Swapping two adjacent letters is counted as two edits (one deletion and one insertion).

Reality: Standard Levenshtein counts swaps as two edits, but Damerau-Levenshtein counts it as one.

Why it matters: Misunderstanding this leads to overestimating the difference between words with common typos, reducing accuracy in spell checkers.

Quick: Is edit distance always symmetric? Commit yes or no.

Common Belief: Edit distance from word A to B is always the same as from B to A.

Reality: Levenshtein distance is symmetric, but some variants or weighted versions may not be symmetric.

Why it matters: Assuming symmetry when it doesn't hold can cause bugs in applications comparing strings.

Quick: Does a zero edit distance mean two strings are identical? Commit yes or no.

Common Belief: Zero edit distance means the two strings are exactly the same.

Reality: Yes, zero means identical strings with no edits needed.

Why it matters: This is a correct belief but often overlooked; it helps quickly check equality using edit distance.

Quick: Can edit distance be negative? Commit yes or no.

Common Belief: Edit distance can be negative if one string is shorter.

Reality: Edit distance is always zero or positive; it counts operations needed, never negative.

Why it matters: Thinking it can be negative leads to incorrect logic and bugs in code.

Expert Zone

1

The choice of cost for insertion, deletion, and substitution can be adjusted to reflect real-world error likelihoods, improving accuracy in applications like OCR or speech recognition.

2

When strings are very long, heuristic or approximate algorithms are used to speed up computation, trading exactness for performance.

3

Backtracking through the DP table can reconstruct the exact sequence of edits, which is useful for highlighting differences or generating correction suggestions.

When NOT to use

Levenshtein distance is not ideal when transpositions are common errors; use Damerau-Levenshtein instead. For very large texts, approximate string matching or hashing techniques like MinHash may be better. Also, it doesn't capture semantic similarity, so for meaning-based comparisons, use embeddings or other NLP methods.

Production Patterns

In spell checkers, Levenshtein distance ranks candidate corrections. In bioinformatics, it compares DNA sequences. In search engines, it helps find close matches to user queries. Optimized implementations use pruning and early stopping to improve speed.

Connections

Dynamic Programming

Levenshtein distance is a classic example of dynamic programming solving overlapping subproblems.

Understanding this algorithm deepens comprehension of dynamic programming principles used widely in optimization problems.

Hamming Distance

Both measure difference between strings, but Hamming distance only counts substitutions and requires equal length strings.

Knowing the difference helps choose the right metric for comparing strings in different contexts.

Genetic Mutation Analysis

Edit distance models mutations in DNA sequences as insertions, deletions, or substitutions.

This connection shows how computer science algorithms help understand biological evolution and disease.

Common Pitfalls

#1 Confusing indices when filling the DP table, causing off-by-one errors.

Wrong approach:

for (let i = 0; i < a.length; i++) {
for (let j = 0; j < b.length; j++) {
// Accessing a[i] and b[j] without adjusting for dp indexing
dp[i][j] = ...
}
}

Correct approach:

for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
// Use a[i-1] and b[j-1] to match dp indices
dp[i][j] = ...
}
}

Root cause:

Misunderstanding that dp table size is (length+1) to include empty prefixes.

#2 Not initializing the first row and column of the DP table.

Wrong approach:

const dp = Array(a.length + 1).fill(null).map(() => Array(b.length + 1).fill(0));
// Missing initialization
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
// fill dp
}
}

Correct approach:

for (let i = 0; i <= a.length; i++) dp[i][0] = i;
for (let j = 0; j <= b.length; j++) dp[0][j] = j;

Root cause:

Forgetting that converting empty string to prefix requires insertions or deletions.

#3 Assuming edit distance works well for semantic similarity.

Wrong approach:

Using edit distance to compare 'car' and 'automobile' expecting a low distance.

Correct approach:

Use semantic similarity models like word embeddings for meaning-based comparison.

Root cause:

Confusing character-level similarity with meaning-level similarity.

Key Takeaways

Edit distance measures how many single-letter edits are needed to change one word into another.

Dynamic programming efficiently computes edit distance by building solutions to smaller problems.

The algorithm uses a table where each cell depends on insertion, deletion, and substitution costs.

Optimizations reduce memory use and extensions handle common errors like letter swaps.

Understanding edit distance is foundational for many applications in text processing and bioinformatics.

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