Wagner-Fisher algorithm to calculate edit distance of two strings

wagnerfisher.go

// Wagner–Fischer a dynamic programming algorithm that computes the edit distance between
// two strings of characters.
//
// Source:
//   http://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
package main

import (
	"fmt"
)

func WagnerFischer(left, right string) int {
	lenL, lenR := len(left), len(right)
	matrix := make([][]int, lenL+1, lenL+1)
	for i := 0; i < lenL+1; i++ {
		matrix[i] = make([]int, lenR+1, lenR+1)
		matrix[i][0] = i
	}
	for i := 0; i < lenR+1; i++ {
		matrix[0][i] = i
	}
	for l := 0; l < lenL; l++ {
		for r := 0; r < lenR; r++ {
			if left[l] == right[r] {
				matrix[l+1][r+1] = matrix[l][r]
				continue
			}
			min := matrix[l][r]           // a substitution
			if matrix[l][r+1] < min {
				min = matrix[l][r+1]  // a deletion
			}
			if matrix[l+1][r] < min {     // an insertion
				min = matrix[l+1][r]
			}			
			matrix[l+1][r+1] = min + 1
		}
	}
	return matrix[lenL][lenR]
}

func main() {
	fmt.Println(WagnerFischer("kitten", "sitting"))
	fmt.Println(WagnerFischer("Saturday", "Sunday"))
}