Dynamic programming minimum edit distance algorithm, implemented in Julia.

min-edit-distance.jl

function min_edit_distance(a :: String, b :: String)
    m = length(a)
    n = length(b)

    D = Array(Uint, m + 1, n + 1)
    F = Array(Uint, m + 1, n + 1)

    for i = 1:m + 1, j = 1:n + 1
        D[i, 1] = i - 1
        D[1, j] = j - 1
        F[i, 1] = 0
        F[1, j] = 0
    end

    for j = 2:n + 1, i = 2:m + 1
        x = D[i - 1, j] + 1
        y = D[i, j - 1] + 1
        z = D[i - 1, j - 1]

        if a[i - 1] != b[j - 1]
            z += 2
        end

        k = min(x, y, z)
        D[i, j] = k

        F[i, j] = 0

        if k == z
            F[i, j] $= 0b001
        else
            if k == y
                F[i, j] $= 0b010
            end

            if k == x
                F[i, j] $= 0b100
            end
        end
    end

    a1 = split(a, "")
    b1 = split(b, "")
    q = m + 1
    r = n + 1
    val = F[q, r];

    while val != 0
        if val & 0b001 == 0b001
            q -= 1
            r -= 1
        elseif val & 0b010 == 0b010
            insert!(a1, q, "*")
            r -= 1
        elseif val & 0b100 == 0b100
            insert!(b1, r, "*")
            q -= 1
        end

        val = F[q, r]
    end

    if q != r
        if q < r
            for i = 1:r - q
                insert!(a1, 1, "*")
            end
        else
            for i = 1:q - r
                insert!(b1, 1, "*")
            end
        end
    end

    return (D[m, n], join(a1,""), join(b1,""))
end

(d, s1, s2) = min_edit_distance("cookies", "pizza")

println(d)
println(s1)
println(s2)

Only the last two columns of the matrix D are ever actually used in computation. This reduces the space used by matrix D to O(m) (from O(mn)). However, because we're still using a O(mn) matrix for the backtrace, the total asymptotic space usage doesn't change.