Solving Edit Distance with Dynamic Programming

1. What is Edit Distance?

The edit distance between two strings is the minimum number of single-character edits required to change one string into the other. The standard Levenshtein distance allows three types of edits:

1. Insertion: Add a character to a string.
2. Deletion: Remove a character from a string.
3. Substitution: Replace one character with another.

Each of these operations is typically assigned a cost of 1. If two characters match, the cost is 0.

To get a clear sense of the problem, let's watch a brief introduction.

2. The Dynamic Programming Formulation

As with other sequence comparison problems, a brute-force approach that tries all possible combinations of edits would be exponentially slow. This is a perfect scenario for dynamic programming due to its overlapping subproblems and optimal substructure.

The Subproblem and Recurrence Relation

We'll define our subproblem using a 2D DP table (let's call it D).
Let D[i][j] be the edit distance between the first i characters of string s1 (i.e., s1[0...i-1]) and the first j characters of string s2 (i.e., s2[0...j-1]).

Our goal is to find D[m][n], where m is the length of s1 and n is the length of s2.

To compute D[i][j], we look at the last characters being compared: s1[i-1] and s2[j-1].

1. If s1[i-1] == s2[j-1] (Characters Match):
   No operation is needed for these characters. The cost is 0. The problem reduces to finding the edit distance between the prefixes s1[0...i-2] and s2[0...j-2].
   Therefore, D[i][j] = D[i-1][j-1].

2. If s1[i-1] != s2[j-1] (Characters Mismatch):
   We must perform an edit, which costs 1. We have three choices, and we take the one with the minimum cost:

   • Substitution: Change s1[i-1] to s2[j-1]. The remaining problem is to transform s1[0...i-2] into s2[0...j-2]. The total cost is 1 + D[i-1][j-1].
   • Deletion: Delete s1[i-1] from s1. The remaining problem is to transform s1[0...i-2] into s2[0...j-1]. The total cost is 1 + D[i-1][j].
   • Insertion: Insert s2[j-1] into s1. The remaining problem is to transform s1[0...i-1] into s2[0...j-2]. The total cost is 1 + D[i][j-1].

We choose the minimum of these three options. So, the full recurrence relation is:

Where δ(a, b) (delta) is 0 if a == b and 1 if a != b.

Base Cases

The base cases handle comparisons with an empty string:

• D[i][0] = i: To transform a prefix of s1 of length i into an empty string, we must perform i deletions.
• D[0][j] = j: To transform an empty string into a prefix of s2 of length j, we must perform j insertions.

The following video provides an excellent, intuitive walkthrough of these three choices and how they relate to the DP table.

3. Solving with the DP Table: A Walkthrough

Now let's apply this logic to fill the table for transforming "horse" into "ros".

1. Initialization: Create a table of size (len("horse")+1) x (len("ros")+1), which is 6x4.

2. Fill Base Cases:

   • The first row D[0][j] will be 0, 1, 2, 3 (inserting "r", "ro", "ros").
   • The first column D[i][0] will be 0, 1, 2, 3, 4, 5 (deleting "h", "ho", "hor", ...).

   The table starts like this:

   	""	"r"	"o"	"s"
   ""	0	1	2	3
   "h"	1	?
   "o"	2
   "r"	3
   "s"	4
   "e"	5

3. Fill the rest of the table: We proceed row by row, column by column. For each cell D[i][j], we apply the recurrence relation.

For a clear, visual demonstration of this process, the next video is very helpful.

4. Tracing the Edits

The bottom-right cell gives us the minimum edit distance, but it doesn't tell us which edits were made. To find the actual sequence of operations, we trace our steps backward from the bottom-right corner to the top-left corner. This is the core of today's learning objective.

At any cell D[i][j], we determine which of the three neighboring cells (D[i-1][j], D[i][j-1], D[i-1][j-1]) was used to compute its value:

• Move Diagonally Up-Left:
  • If s1[i-1] == s2[j-1], this move corresponds to a match.
  • If s1[i-1] != s2[j-1], this move corresponds to a substitution.
• Move Up: This corresponds to a deletion of s1[i-1].
• Move Left: This corresponds to an insertion of s2[j-1].

By following the path of minimums, we reconstruct the sequence of edits in reverse order. Note that sometimes multiple paths exist, meaning there are several optimal ways to perform the edits.

This image shows a completed DP table with a traceback path highlighted.

Now, let's see a video demonstrating this backtracking process.

5. Complexity and Implementation

• Time Complexity: We need to fill every cell of an m x n table, and each calculation is a constant-time operation. Therefore, the time complexity is $O(m\times n)$.
• Space Complexity: We need to store the m x n table, so the space complexity is $O(m\times n)$.
  • Note: Just like with LCS, if you only need the distance and not the traceback, the space can be optimized to $O(\min (m,n))$ because computing a row only requires the information from the previous row.

The video LINK also provides a full Python implementation including the traceback logic in its final section (from 07:33), which you can review if you're interested in the code details.

Conclusion

In this lesson, we dissected the Edit Distance problem and developed a robust solution using dynamic programming.

Key Takeaways:

• Edit distance measures the minimum edits (insert, delete, substitute) to transform one string into another.
• The problem is solved using a 2D DP table where D[i][j] stores the edit distance between prefixes of the two strings.
• The recurrence relation considers three possibilities at each step: insertion (from the left cell), deletion (from the top cell), and substitution/match (from the diagonal cell).
• By backtracking from the final cell in the table, we can reconstruct the exact sequence of edits that yields the minimum distance.

Preview of the Next Lesson:
We will conclude our module on classic DP applications by examining the Coin Change problem. This problem presents a different DP pattern, where we aim to find the number of ways to make change for a target amount using a given set of coin denominations. It's less about sequence alignment and more about counting combinations.