LeetCode Q72: Edit Distance (hard)

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

A classic DP problem.

Suppose DP[ i ][ j ] save the steps needed by converting word1[ 0 : i ] to word2[ 0 : j ]. Let's consider the very last step needed before word1[ 0 : i ] can be converted to word2[ 0 : j ].

If the step is DELETE, means word1[ 0 : i-1 ] = word2[ 0 : j ]. Thus DP[ i ][ j ] = DP[ i -1 ][ j ] + 1.

If the step is INSERT,  means word1[ 0 : i ] = word2[ 0 : j-1]. Thus DP[ i ][ j ] = DP[ i ][ j-1 ] + 1.

if the step is REPLACE, there could be two possibilities.

    First, if word1[ i ] = word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ].

    Second, if word[ i ] != word2[ j ], then DP[ i ][ j ] = DP[ i-1 ][ j-1 ] + 1.

So, by taking minimum of these three possibilities, we get the value of DP[ i ][ j ].

To, initialize the boundary case, from above examples we know, to get DP[ i ][ j ], we basically, need to solve the values on it up left, left, and up. So, we only need to initialize the first row and the first column of the table DP.