LeetCode 72 Edit Distance - Implementation

Here's the full solution:

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: $O(mn)$. Space: $O(mn)$, reducible to $O(n)$.

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.