Understanding the bottom up solution to the edit distance problem

To solve the edit distance problem using a bottom-up dynamic programming approach, we fill a table iteratively beginning from the smallest subproblems and building towards the final answer. As with any bottom-up solution, we process subproblems in an order that guarantees every result we depend on has already been computed and stored before we need it.

The bottom up solution

When implementing the recurrence relation using a top-down algorithm, i and j are indices into s1 and s2, and the base case occurs when either index drops below 0. If i < 0, the solution is j + 1 (we need j + 1 insertions to build the remaining prefix of s2); if j < 0, the solution is i + 1 (we need i + 1 deletions to remove the remaining prefix of s1).

For the recurrence relations, i < 0 and j < 0 serve as the base cases.

However, arrays cannot have negative indices. To handle this cleanly in the bottom-up table, we shift the meaning of i and j so that they represent the number of characters considered from each string rather than indices. This way, the base case becomes i == 0 or j == 0, which maps naturally to row 0 and column 0 of the table.

How does this shift change the recurrence?

The recurrence relation itself does not change, we still check whether the last characters match and either carry forward the previous value or take the minimum of insert, delete, and replace. The only difference is that when i represents the number of characters considered, the last character of the prefix is at index i - 1 in the string (instead of index i). This is purely a shift in how we index into the table and the strings, not a change in logic.

We can use i and j to denote the number of characters considered from the start, instead of the index of the last character.

We create a 2D integer array editDistance of dimensions (m + 1) × (n + 1), where editDistance[i][j] stores the minimum number of edit operations needed to transform the first i characters of s1 into the first j characters of s2.