Lua编辑距离：两串差异的量化步数

-- 错误：只做前缀包含比对，变体全漏
function like(word, bad)
    return word:find(bad, 1, true) ~= nil
end

local function editDist(a, b)
    local m, n = #a, #b
    local dp = {}
    for i = 0, m do dp[i] = {[0] = i} end
    for j = 0, n do dp[0][j] = j end
    for i = 1, m do
        for j = 1, n do
            local cost = a:sub(i, i) == b:sub(j, j)
                and 0 or 1
            dp[i][j] = math.min(dp[i - 1][j] + 1,
                dp[i][j - 1] + 1,
                dp[i - 1][j - 1] + cost)
        end
    end
    return dp[m][n]
end
local p = getplayerbyname("edt01")
sendmsg(p, 1, editDist("kitten", "sitting"))