Skip to content

Instantly share code, notes, and snippets.

@jameskeane
Created July 6, 2011 23:42
Show Gist options
  • Save jameskeane/1068610 to your computer and use it in GitHub Desktop.
Save jameskeane/1068610 to your computer and use it in GitHub Desktop.
Levenshtein Distance
func min(a1 int, a2 int, a3 int) int {
min := a1
if a2 < min {
min = a2
}
if a3 < min {
min = a3
}
return min
}
func make2d(l1 int, l2 int) [][]int {
ret := make([][]int, l1)
for i := 0; i < l1; i++ {
ret[i] = make([]int, l2)
}
return ret
}
func LevenshteinDistance(str1 string, str2 string) int {
distance := make2d(len(str1)+1, len(str2)+1)
for i := 0; i <= len(str1); i++ {
distance[i][0] = i;
}
for i := 0; i <= len(str2); i++ {
distance[0][i] = i;
}
for i := 1; i <= len(str1); i++ {
for j := 1; j <= len(str2); j++ {
ex := 1
if str1[i - 1] == str2[j - 1] {
ex = 0
}
distance[i][j] = min(distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] + ex)
}
}
return distance[len(str1)][len(str2)]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment