levensthein distance code example

Example 1: levenshtein distance

package main

import "fmt"

// levenshtein distance in Golang
func levenshtein(str1, str2 []rune) int {
	s1len := len(str1)
	s2len := len(str2)
	column := make([]int, len(str1)+1)
	for y := 1; y <= s1len; y++ {
		column[y] = y
	}
	for x := 1; x <= s2len; x++ {
		column[0] = x
		currkey := x - 1
		for y := 1; y <= s1len; y++ {
			oldkey := column[y]
			incr := 0
			if str1[y-1] != str2[x-1] {
				incr = 1
			}
			column[y] = min3(column[y]+1, column[y-1]+1, currkey+incr)
			currkey = oldkey
		}
	}
	return column[s1len]
}

func min3(a, b, c int) int {
	if a < b {
		if a < c { return a }
	} else {
		if b < c { return b }
	}
	return c
}

func main(){
	var str1, str2 = []rune("Monday"), []rune("Friday")
	fmt.Printf("Distance between Monday and Friday = %d\n", levenshtein(str1, str2))  // 3
}

Example 2: levensthein distance

function levenshtein(s, t) {
  if(s.length === 0) return t.length; 
  if(t.length === 0) return s.length;    
  let m = new Array(s.length + 1).fill(0).map(
    (_, i) => new Array(t.length + 1).fill(0).map(
      (_,j) => i*j ? 0 : i+j
    )
  )
  for(let i = 1; i <= s.length; i++) {
    for(let j = 1; j <= t.length; j++) {
      if(s[i - 1] === t[j - 1]) {
        m[i][j] = m[i-1][j-1]
      } else {
        m[i][j] = Math.min(m[i - 1][j - 1], m[i - 1][j], m[i][j - 1]) + 1
      }
    }
  }
  return m[s.length][t.length]
} 

console.log("Distance between Monday and Friday = %d\n", levenshtein("Monday", "Friday"));  // 3

Example 3: levenshtein distance

def levenshtein(a, b):
    m = [[*range(len(a) + 1)] for _ in range(len(b) + 1)]
    for i in range(len(b) + 1):
        m[i][0] = i
    for i in range(1, len(b) + 1):
        for j in range(1, len(a) + 1):
            m[i][j] = min(m[i-1][j] + 1, m[i][j-1] + 1, m[i-1][j-1] + (b[i-1] != a[j-1]))
    return m[-1][-1]