Problem
Input: two strings and 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 to , an alignment tells us what characters are missing from , and what are missing from , 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
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 and .
High-level question
What is the first column? We have three finite answers: either both and , either and , or and .
- : the subproblem is to align .
- : the subproblem is to align .
- : the subproblem is to align .
-function
We generalize the subproblems encountered above. We can define a function which equals the min cost alignment of and . Here, varies between , and varies between .
Recursively, we now have three cases to consider, because there are three possible subproblems to recurse on.
Runtime analysis
There are subproblems, and it takes to compute the edit for each subproblem. So total runtime is given by .