Here's the full solution:
plaintext function minDistance(word1, word2) m := length of word1 n := length of word2 dp := 2D (two-dimensional) array of size (m + 1) x (n + 1) for i from 0 to m dp[i][0] := i // delete all chars from word1 for j from 0 to n dp[0][j] := j // insert all chars into empty string for i from 1 to m for j from 1 to n if word1[i - 1] = word2[j - 1] dp[i][j] := dp[i - 1][j - 1] else dp[i][j] := 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) return dp[m][n]
Time: . Space: , reducible to .
The three operations map to: delete (dp[i-1][j]), insert (dp[i][j-1]), replace (dp[i-1][j-1]). When characters match, no operation is needed.