Problem

Input:two strings $A[1..n]$ and $B[1..m]$ where each index is a character

Output:how many edits can we make? An edit is considered either an insertion of a character, deletion of a character, or substitution.

## Alignment

If we want to go from $A$ to $B$, an alignment tells us what characters are missing from $B$, and what are missing from $A$, and do both have. Let’s use character $⊥$ as “blank,” meaning one string doesn’t have a character that the other does.

Given an alignment, the number of edits is given by

$i=1∑l 1{ifl-th column is unequal}$The solution space is the set of all alignments. The objective is the cost function (number of edits) from an input alignment. The constants are the alignment of $A$ and $B$.

## High-level question

What is the first column? We have three *finite* answers: either both $A[1]$ and $B[1]$, either $A[1]$ and $⊥$, or $⊥$ and $B[1]$.

- $(A[1],B[1])$: the subproblem is to align $A[2..n],B[2..m]$.
- $(A[1],⊥)$: the subproblem is to align $A[2..n],B[1..m]$.
- $(⊥,B[1])$: the subproblem is to align $A[1..n],B[2..m]$.

## $G$-function

We generalize the subproblems encountered above. We can define a function $G(i,j)$ which equals the min cost alignment of $A[i..n]$ and $B[j..m]$. Here, $i$ varies between $1..n$, and $j$ varies between $1..m$.

Recursively, we now have three cases to consider, because there are three possible subproblems to recurse on.

$G(i,j)=⎩⎨⎧ 1+G(i+1,j)1+G(i,j+1)1{A[i]=B[i]}+G(i+1,j+1) ifAhas a letter,Bdoesn’tifBhas a letter,Adoesn’tif both have a letter $## Runtime analysis

There are $mn$ subproblems, and it takes $O(1)$ to compute the edit for each subproblem. So total runtime is given by $O(mn)$.