出處：這里和這里

 #判斷兩個(gè)字符串從不相同到相同最少需要幾次變化（增加字符、刪除字符、替換字符）
  def levenshtein_distance(s, t)
    m = s.length
    n = t.length
    return m if n == 0
    return n if m == 0
    #初始化一個(gè)二維數(shù)組，行數(shù)是s字符串的長(zhǎng)度+1，列數(shù)是t字符串的長(zhǎng)度+1
    d = Array.new(m+1) {Array.new(n+1)}
    #將第一行和第一列的值初始化。
    #d[m][0]表示從一個(gè)空字符串變成與s相等的字符串最少需要幾步
    #d[0][n]表示從一個(gè)空字符串變成與t相等的字符串最少需要幾步
    #d[0][0]表示兩個(gè)空字符串需要0步就相等了
    (0..m).each {|i| d[i][0] = i}
    (0..n).each {|j| d[0][j] = j}
    #至此，數(shù)據(jù)初始化結(jié)束，因?yàn)槎嗔艘恍泻鸵涣?，每一個(gè)交叉點(diǎn)，比如d[i][j]的左方向、上方向以及左上角都有一個(gè)值，
    # 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
        #如果不相同，則計(jì)算刪除字符串、增加字符串、替換字符串經(jīng)過的步數(shù)。
          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]的值越大，表示兩個(gè)字符串變成相同所需要經(jīng)過的步數(shù)越多，意味著兩個(gè)字符串越不相似
    d[m][n]
  end