Editorial (icecuber) (C++)

CPH 7.5 (Edit Distance)

Explanation

We begin by initializing a $\texttt{dp}$ array, where $\texttt{dp}[i][j]$ is the minimum number of edits to convert the first $i$ characters of the first string, which we denote as $\texttt{str1}$, into the first $j$ characters of the second string, which we denote as $\texttt{str2}$. The base cases in the $\texttt{dp}$ array occur when one of the prefixes is empty.

This means we initialize the $\texttt{dp}$ array as follows. Initialize $\texttt{dp}[i][0],$ where $i$ is the length of the prefix in $\texttt{str1}$, to be $i$ because it takes a minimum of $i$ deletions to convert the first $i$ characters into the first $0$ characters of $\texttt{str2}$ (an empty string). Similarly, initialize $\texttt{dp}[0][j],$ where $j$ is the length of the prefix in $\texttt{str2}$, to be $j$ because it takes $j$ insertions to convert the first $0$ characters of $\texttt{str1}$ (also an empty string) into the first $j$ characters of $\texttt{str2}$.

Now that we have initialized our $\texttt{dp}$ array, we can move onto the $\texttt{dp}[i][j]$ transition. The options we have are to delete, insert, or replace a character from $\texttt{str1}$, or do nothing if the current characters are already equal.

When we delete a character, we convert $\texttt{str1}[:i-1]$ into $\texttt{str2}[:j]$, and then delete $\texttt{str1}[i-1]$. Therefore, this means that, if the last operation is a deletion, $\texttt{dp}[i][j]$ is equal to $\texttt{dp}[i - 1][j] + 1$, where the extra $1$ is the cost of the delete operation.

When we insert a character, we effectively convert $\texttt{str1}[:i]$ into $\texttt{str2}[:j-1]$, and then insert $\texttt{str2}[j-1]$. So, $\texttt{dp}[i][j]$ is equal to $\texttt{dp}[i][j-1] + 1$, where the extra $1$ is the cost of the insert operation.

Finally, when we replace a character, we essentially convert $\texttt{str1}[:i-1]$ into $\texttt{str2}[:j-1]$, then handle the last character. If $\texttt{str1}[i-1]$ and $\texttt{str2}[j-1]$ are different, then that counts as a replacement operation. So, the replacement operation can be represented compactly as

where $\texttt{str1}[i - 1] \neq \texttt{str2}[j - 1]$ is only $1$ when we actually need to replace the letter.

Combining the transition for each operation, the minimum number of edits required to convert the first $i$ characters in $\texttt{str1}$ into the first $j$ characters of $\texttt{str2}$ is

Using this transition, since each state depends only on the cell above, the cell to the left, and the diagonal upper-left cell, we fill the table from top to bottom and left to right. Our final answer is $\texttt{dp}[n][m].$

Implementation

Time Complexity: $\mathcal{O}(NM)$

Copy
str1 = input()
str2 = input()

"""
dp[i][j] is the minimum number of moves to change the first i letters
of the string into the first j letters of result.
"""
dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

# i edits needed to convert first i chars of string 1 into empty string