Levenshtein distance

Levenstein.rb

class String
  
  def levenstein(other, ins=2, del=1, sub=1)
    
    return nil if self.nil? || other.nil?
    
    dm = []
    dm[0] = (0..self.length).collect { |i| i * ins}
    fill = [0] * (self.length - 1)
    
    for i in 1..other.length
      dm[i] = [i * del, fill.flatten] 
    end
    
    for i in 1..other.length
      for j in 1..self.length
        dm[i][j] = [
          dm[i-1][j-1] + (self[i-1] == other[i-1] ? 0 : sub),
          dm[i][j-1] + ins,
          dm[i-1][j] + del
          ].min
      end
    end
    
    dm[other.length][self.length]
  end
  
  def similar?(other, thresh = 2)
    self.levenstein(other) < thresh
  end

end


puts "Foobar".similar?("Fuubar", 3)