Edit Distance Problem Levenshtein in DSA Typescript - Execution Trace

Concept Flow - Edit Distance Problem Levenshtein

Start with two strings

↓

Create DP table with size (m+1)x(n+1)

↓

Initialize first row and column

↓

For each cell (i,j):

↓

Compare characters s1[i-1

↓

Copy diagonal

↓

Fill table row by row

↓

Result at dp[m

We build a table to find the minimum edits to convert one string to another by comparing characters and choosing the best operation step by step.

Execution Sample

DSA Typescript

const s1 = "kitten";
const s2 = "sitting";
// dp[i][j] = edit distance between s1[0..i-1] and s2[0..j-1]

This code calculates the minimum edits to change 'kitten' into 'sitting' using a table.

Execution Table

Step	Operation	Indices (i,j)	Characters Compared	DP Cell Value	DP Table Snapshot
1	Initialize dp[0][0]	(0,0)	N/A	0	[[0]]
2	Initialize first row	(0,j)	N/A	j	[[0,1,2,3,4,5,6,7]]
3	Initialize first column	(i,0)	N/A	i	[[0],[1],[2],[3],[4],[5],[6]]
4	Compare 'k' and 's'	(1,1)	'k' vs 's'	1	[[0,1,2,3,4,5,6,7],[1,1]]
5	Compare 'k' and 'i'	(1,2)	'k' vs 'i'	2	[...,[1,1,2]]
6	Compare 'k' and 't'	(1,3)	'k' vs 't'	3	[...,[1,1,2,3]]
7	Compare 'k' and 't'	(1,4)	'k' vs 't'	4	[...,[1,1,2,3,4]]
8	Compare 'k' and 'i'	(1,5)	'k' vs 'i'	5	[...,[1,1,2,3,4,5]]
9	Compare 'k' and 'n'	(1,6)	'k' vs 'n'	6	[...,[1,1,2,3,4,5,6]]
10	Compare 'k' and 'g'	(1,7)	'k' vs 'g'	7	[...,[1,1,2,3,4,5,6,7]]
11	Compare 'i' and 's'	(2,1)	'i' vs 's'	2	[...,[2,2]]
12	Compare 'i' and 'i'	(2,2)	'i' vs 'i'	1	[...,[2,1]]
13	Compare 'i' and 't'	(2,3)	'i' vs 't'	2	[...,[2,1,2]]
14	Compare 'i' and 't'	(2,4)	'i' vs 't'	3	[...,[2,1,2,3]]
15	Compare 'i' and 'i'	(2,5)	'i' vs 'i'	4	[...,[2,1,2,3,4]]
16	Compare 'i' and 'n'	(2,6)	'i' vs 'n'	5	[...,[2,1,2,3,4,5]]
17	Compare 'i' and 'g'	(2,7)	'i' vs 'g'	6	[...,[2,1,2,3,4,5,6]]
...	...	...	...	...	...
Last	Final result	(6,7)	N/A	3	Full dp table with dp[6][7] = 3

💡 All dp cells filled; dp[m][n] = 3 means minimum 3 edits needed

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 10	After Step 17	Final
dp	Empty	First row filled with 0..7	First column filled with 0..6	Partial table filled up to row 1	Partial table filled up to row 2	Full table filled with final value 3 at dp[6][7]
i	0	0	1	1	2	6
j	0	1	0	7	7	7
Current chars	N/A	N/A	'k' vs 's'	'k' vs 'g'	'i' vs 'g'	N/A

Key Moments - 3 Insights

Why do we initialize the first row and first column of the dp table?

The first row and column represent converting an empty string to a prefix of the other string, so the cost is just the length of that prefix (all insertions or deletions). See steps 2 and 3 in the execution_table.

Why do we take the minimum of insert, delete, and replace plus one when characters differ?

Because each operation costs 1, and we want the minimal total edits. We check all three options and pick the smallest. This is shown in steps like 4 and 12 where characters differ or match.

Why does dp[m][n] give the final edit distance?

Because dp[i][j] stores the minimum edits to convert s1[0..i-1] to s2[0..j-1]. So dp[m][n] covers the full strings. See the last step in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the dp cell value for dp[1][1] comparing 'k' and 's'?

A 1

B 0

C 2

D Undefined

💡 Hint

Check the 'DP Cell Value' column at step 4 in execution_table.

At which step does the dp table first show a character match with value copied from diagonal?

A Step 4

B Step 2

C Step 12

D Step 17

💡 Hint

Look for steps where characters compared are equal and dp cell value is less than neighbors, see step 12.

If we changed s2 from 'sitting' to 'kitten', what would happen to dp[6][7] in the final table?

A It would stay 3

B It would be 0

C It would increase

D It would be undefined

💡 Hint

If both strings are identical, edit distance is zero, so dp[m][n] = 0.

Concept Snapshot

Edit Distance (Levenshtein) finds minimum edits to convert one string to another.
Use a 2D dp table of size (m+1)x(n+1).
Initialize first row and column with 0..length.
Fill dp[i][j] by comparing chars:
  if equal: dp[i][j] = dp[i-1][j-1]
  else: dp[i][j] = 1 + min(insert, delete, replace)
Result at dp[m][n].

Full Transcript

The Edit Distance Problem (Levenshtein) calculates the minimum number of edits needed to change one string into another. We use a two-dimensional table where each cell dp[i][j] represents the minimum edits to convert the first i characters of the first string to the first j characters of the second string. We start by initializing the first row and column because converting from or to an empty string requires insertions or deletions equal to the length of the other string. Then, for each cell, we compare the characters of the two strings. If they match, we copy the diagonal value. If not, we take the minimum of the three possible operations (insert, delete, replace) plus one. After filling the table, the bottom-right cell gives the final minimum edit distance. This method ensures we consider all possible ways to transform one string into another 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