class String

Public Instance Methods

levenshtein(string) click to toggle source

Stolen from: en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Ruby

# File lib/string.rb, line 4
def levenshtein(string)
  matrix = [(0..self.length).to_a]
  (1..string.length).each do |j|
    matrix << [j] + [0] * (self.length)
  end

  (1..string.length).each do |i|
    (1..self.length).each do |j|
      if self[j-1] == string[i-1]
        matrix[i][j] = matrix[i-1][j-1]
      else
        matrix[i][j] = [
          matrix[i-1][j],
          matrix[i][j-1],
          matrix[i-1][j-1],
        ].min + 1
      end
    end
  end
  return matrix.last.last
end