## levenshtein distance

in ruby

### Source Code

``````def levenshtein(string_a = "", string_b = "")
# Size of the two strings
len_a = string_a.size
len_b = string_b.size

# Return the length of the unique array if is only
# one parameter
return len_b if len_a == 0
return len_a if len_b == 0

# Hash for the values
map =  Hash.new(0)

# Loop on all the elements of string_a to fill map
for i in 1..len_a do
map[[i, 0]] = i
end
# Loop on all the elements of string_b to fill map
for j in 1..len_b do
map[[0, j]] = j
end

# Iterate over the whole map
for i in 1..len_a do
for j in 1..len_b  do
# Check the cost
cost = (string_a[i-1] == string_b[j-1]) ? 0 : 1;
# Clean and readable way for the variables
deletion = map[[i-1, j]] + 1
insertion = map[[i, j-1]] + 1
substitution = map[[i-1, j-1]] + cost
# Fill with the minimum value
map[[i,j]] = [deletion, insertion, substitution].min
end
end
return map[[len_a, len_b]]
end
``````
``````require "./levenshtein.rb"

describe "levenshtein" do
context "When has zero argument" do
it{ expect(levenshtein()).to eq 0 }
end

context "When has one argument" do
it{ expect(levenshtein("MÃ©xico")).to eq 6 }
end

context "When has Godfather and Godfather" do
it{ expect(levenshtein("Godfather", "Godfather")).to eq 0 }
end

context "When has Godfather and Godfather" do
it{ expect(levenshtein("Godfather", "Godfather")).to eq 0 }
end

context "When has Godfather and Godfathe" do
it{ expect(levenshtein("Godfather", "Godfathe")).to eq 1 }
end

context "When has Godfather and odfather" do
it{ expect(levenshtein("Godfather", "odfather")).to eq 1 }
end

context "When has Godfather and Gdfthr" do
it{ expect(levenshtein("Godfather", "Gdfthr")).to eq 3 }
end

context "When has kitten and sitten" do
it{ expect(levenshtein("kitten", "sitting")).to eq 3 }
end

context "When has horse and ros" do
it{ expect(levenshtein("horse", "ros")).to eq 3 }
end

context "When has GUMBO and GAMBOL" do
it{ expect(levenshtein("GUMBO", "GAMBOL")).to eq 2 }
end

end
``````