Levenshtein Distance

Levenshtein.go

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)]
	
}