Edit Distance - Implementation

Here is the implementation for Edit Distance (CSES 1639):

function editDistance(A, B)
    n := length of A
    m := length of B
    dp := 2D array of size (n + 1) × (m + 1)

    // Base cases
    for i from 0 to n
        dp[i][0] := i
    for j from 0 to m
        dp[0][j] := j

    // Fill table
    for i from 1 to n
        for j from 1 to m
            if A[i] = B[j] then
                dp[i][j] := dp[i - 1][j - 1]
            else
                replace := dp[i - 1][j - 1] + 1
                delete := dp[i - 1][j] + 1
                insert := dp[i][j - 1] + 1
                dp[i][j] := min(replace, delete, insert)

    return dp[n][m]

The three operations map directly to three neighbors in the table. Replace looks diagonally, delete looks up, insert looks left. When characters match, you take the diagonal value for free. Trace editDistance("CAT", "CUT"): the table fills to dp[3][3] = 1 (replace A with U).

Time complexity: $O(n \cdot m)$.

Space complexity: $O(n \cdot m)$, reducible to $O(m)$ by keeping only two rows.