Skip to content

Instantly share code, notes, and snippets.

@jbowles
Last active December 19, 2015 01:28
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jbowles/5876127 to your computer and use it in GitHub Desktop.
Save jbowles/5876127 to your computer and use it in GitHub Desktop.
Part one of Levenshtein distance
package main
import "fmt"
// http://en.wikipedia.org/wiki/Levenshtein_distance
// FIRST PART: define vector/cell for the dynamic programming table based on string lengths
func PartOneLevenshtein(s1, s2 string) {
m := len(s1)
n := len(s2)
width := n - 1
vector := make([]int, m * n)
// cells for i of m(s1)
for i := 1; i < m; i++ {
vector[i * width + 0] = i
fmt.Println("i+=",i, "for len(str1)==",m, "at vector cell", vector[i * width + 0]*width)
}
// cell for j of n(s2)
for j := 1; j < n; j++ {
vector[0 * width + j] = j
fmt.Println("j+=",j, "for len(str2)==",n, "at vector cell", vector[0 * width + j])
}
fmt.Println("total vecotr:",vector)
}
func main() {
PartOneLevenshtein("0123456789","0123")
}
/*
*** OUTPUT
i+= 1 for len(str1)== 10 at vector cell 3
i+= 2 for len(str1)== 10 at vector cell 6
i+= 3 for len(str1)== 10 at vector cell 9
i+= 4 for len(str1)== 10 at vector cell 12
i+= 5 for len(str1)== 10 at vector cell 15
i+= 6 for len(str1)== 10 at vector cell 18
i+= 7 for len(str1)== 10 at vector cell 21
i+= 8 for len(str1)== 10 at vector cell 24
i+= 9 for len(str1)== 10 at vector cell 27
j+= 1 for len(str2)== 4 at vector cell 1
j+= 2 for len(str2)== 4 at vector cell 2
j+= 3 for len(str2)== 4 at vector cell 3
total vecotr: [0 1 2 3 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 7 0 0 8 0 0 9 0 0 0 0 0 0 0 0 0 0 0 0]
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment