判断两个字符串从不相同到相同最少需要几次变化

出处：这里和这里

 #判断两个字符串从不相同到相同最少需要几次变化（增加字符、删除字符、替换字符）
  def levenshtein_distance(s, t)
    m = s.length
    n = t.length
    return m if n == 0
    return n if m == 0
    #初始化一个二维数组，行数是s字符串的长度+1，列数是t字符串的长度+1
    d = Array.new(m+1) {Array.new(n+1)}
    #将第一行和第一列的值初始化。
    #d[m][0]表示从一个空字符串变成与s相等的字符串最少需要几步
    #d[0][n]表示从一个空字符串变成与t相等的字符串最少需要几步
    #d[0][0]表示两个空字符串需要0步就相等了
    (0..m).each {|i| d[i][0] = i}
    (0..n).each {|j| d[0][j] = j}
    #至此，数据初始化结束，因为多了一行和一列，每一个交叉点，比如d[i][j]的左方向、上方向以及左上角都有一个值，
    # d.each {|ele| p ele}
    #开始遍历
    (1..n).each do |j|
      (1..m).each do |i|
        #判断同位置的字符是否相同，相同的话，就将左上角位置的值写入。表示本次比较并不需要任何操作
        if s[i-1] == t[j-1]  # adjust index into string
          d[i][j] = d[i-1][j-1]       # no operation required
        else
        #如果不相同，则计算删除字符串、增加字符串、替换字符串经过的步数。
          d[i][j] = [ d[i-1][j]+1,    # deletion 删除
                      d[i][j-1]+1,    # insertion 增加
                      d[i-1][j-1]+1,  # substitution 替换
                    ].min
        end
      end
    end
    #d[m][n]的值越大，表示两个字符串变成相同所需要经过的步数越多，意味着两个字符串越不相似
    d[m][n]
  end