Class: String

Inherits:
Object
  • Object
show all
Defined in:
lib/string.rb

Instance Method Summary collapse

Instance Method Details

#levenshtein(string) ⇒ Object

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



4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
# 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