Edit Distance with Full Table

package main

import "fmt"

func editDistance(s1, s2 string) int {
	m, n := len(s1), len(s2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][0] = i
	}
	for j := 0; j <= n; j++ {
		dp[0][j] = j
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s1[i-1] == s2[j-1] {
				dp[i][j] = dp[i-1][j-1]
			} else {
				dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
			}
		}
	}
	// print table
	fmt.Printf("    ")
	for j := 0; j < n; j++ {
		fmt.Printf("  %c", s2[j])
	}
	fmt.Println()
	for i := 0; i <= m; i++ {
		if i == 0 {
			fmt.Printf("  ")
		} else {
			fmt.Printf("%c ", s1[i-1])
		}
		for j := 0; j <= n; j++ {
			fmt.Printf("%2d ", dp[i][j])
		}
		fmt.Println()
	}
	return dp[m][n]
}

func main() {
	d := editDistance("horse", "ros")
	fmt.Printf("Distance: %d\n", d)
	//       r  o  s
	//    0  1  2  3
	// h  1  1  2  3
	// o  2  2  1  2
	// r  3  2  2  2
	// s  4  3  3  2
	// e  5  4  4  3
	// Distance: 3
}