# @param {String} word1
# @param {String} word2
# @return {Integer}
def min_distance(word1, word2)
    m=word1.size;n=word2.size
    d=(1+m).times.map{[0]*(1+n)}
    (1..m).each{|i|d[i][0]=i}
    (1..n).each{|i|d[0][i]=i}
    (1..m).each do|i|
        (1..n).each do|j|
            sc=(word1[i-1]==word2[j-1] ? 0:1)
            d[i][j]=[d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+sc].min
        end
    end
    p d
    d[m][n]
end