Edit Distance (ED)

The Edit Distance (ED) problem, also known as the Levenshtein distance, measures the minimum number of operations required to transform one string into another. These operations typically include insertion, deletion, or substitution of a single character.

• Of course it is a Leetcode question: 72. Edit Distance. Do it.

From CS341

1. Types of Mispelling:
   • Character typed wrong: Requires a replacement operation.
   • Character missed: Requires an addition operation.
   • Extra character typed: Requires a deletion operation.
2. Alignment:
   • The first step is to align the two strings. This involves inserting gaps to match the lengths of the strings.
3. Calculating Edit Distance:
   • Three cases may occur:
     1. Aligning the last character of $A$ with the last character of $B$.
        • If $A[n]=B[m]$, no additional cost is incurred.
        • If $A[n]\ne B[m]$, an additional cost of $1$ is incurred.
        • Recursively calculate the edit distance between $A[\mathrm{1..}n-1]$ and $B[\mathrm{1..}m-1]$.
     2. $A_n$ is not aligned with $B_m$.
        • Incur an additional cost of $1$ (deletion or addition).
        • Recursively calculate the edit distance between $A[\mathrm{1..}n-1]$ and $B[\mathrm{1..}m]$.
     3. $B_n$ is not aligned with $A_n$ at the end.
        • Incur an additional cost of $1$ (deletion or addition).
        • Recursively calculate the edit distance between $A[\mathrm{1..}n]$ and $B[\mathrm{1..}m-1]$.
4. Dynamic Programming:
   • Define an array $D$ of size $(n+1)\times (m+1)$ to store the edit distances between substrings of $A$ and $B$.
   • Use dynamic programming to fill in the array $D$ based on the recursive relations described above.
   • Base cases: The edit distance between an empty string and a non-empty string is the length of the non-empty string, and vice versa.
   • The solution lies in the bottom-right cell of the array $D$.

The recurrence relation provided defines the edit distance between two strings $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$ in terms of smaller subproblems. Here’s a breakdown of the recurrence:

• Let $D[i,j]$ be the edit distance between the prefixes $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j]$.
• Base cases:
  • $D[0,j]=j$: The edit distance between an empty string and $B[\mathrm{1..}j]$ is $j$ because it requires adding $j$ characters to transform the empty string into $B[\mathrm{1..}j]$.
  • $D[i,0]=i$: The edit distance between $A[\mathrm{1..}i]$ and an empty string is $i$ because it requires deleting $i$ characters from $A[\mathrm{1..}i]$ to make it empty.
• Recurrence relation:
  • $D[i,j]$ is the minimum of three values:
    1. $D[i-1,j-1]+1$ if $A[i]\ne B[j]$: This corresponds to a substitution operation where $A[i]$ is replaced by $B[j]$.
    2. $D[i-1,j]+1$: This corresponds to a deletion operation where $A[i]$ is deleted, and we find the edit distance between $A[\mathrm{1..}i-1]$ and $B[\mathrm{1..}j]$.
    3. $D[i,j-1]+1$: This corresponds to an insertion operation where $B[j]$ is added to $A$, and we find the edit distance between $A[\mathrm{1..}i]$ and $B[\mathrm{1..}j-1]$.
• The algorithm computes all $D[i,j]$ values using two nested loops, iterating over all possible prefixes of the strings $A$ and $B$, resulting in a runtime of $\Theta (mn)$, where $m$ and $n$ are the lengths of the strings $A$ and $B$ respectively.