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 .