levenshtein distance algorithm 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: levenshtein distance

fn levenshtein(word1: &str, word2: &str) -> usize {
    let s = word1.chars().collect::<Vec<_>>();
    let t = word2.chars().collect::<Vec<_>>();
    let slength = s.len() + 1;
    let tlength = t.len() + 1;
    let mut m = vec![vec![0]];
    for i in 1..slength { m[0].push(i); }
    for j in 1..tlength { m.push(vec![j]); }
    
    for j in 1..tlength {
        for i in 1..slength {
            let tmp: usize = if s[i-1] == t[j-1] {
                m[j-1][i-1]
                } else {
                1 + std::cmp::min(
                std::cmp::min(m[j][i-1], m[j-1][i])
                , m[j-1][i-1])
            };
            m[j].push(tmp);
        }
    }
    m[tlength-1][slength-1]
}
    
fn main() {
    println!("{}", levenshtein("Monday", "Friday"));  // 3
}

Tags:

Go Example