1def levenshtein(a, b):
2 m = [[*range(len(a) + 1)] for _ in range(len(b) + 1)]
3 for i in range(len(b) + 1):
4 m[i][0] = i
5 for i in range(1, len(b) + 1):
6 for j in range(1, len(a) + 1):
7 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]))
8 return m[-1][-1]
1package main
2
3import "fmt"
4
5// levenshtein distance in Golang
6func levenshtein(str1, str2 []rune) int {
7 s1len := len(str1)
8 s2len := len(str2)
9 column := make([]int, len(str1)+1)
10 for y := 1; y <= s1len; y++ {
11 column[y] = y
12 }
13 for x := 1; x <= s2len; x++ {
14 column[0] = x
15 currkey := x - 1
16 for y := 1; y <= s1len; y++ {
17 oldkey := column[y]
18 incr := 0
19 if str1[y-1] != str2[x-1] {
20 incr = 1
21 }
22 column[y] = min3(column[y]+1, column[y-1]+1, currkey+incr)
23 currkey = oldkey
24 }
25 }
26 return column[s1len]
27}
28
29func min3(a, b, c int) int {
30 if a < b {
31 if a < c { return a }
32 } else {
33 if b < c { return b }
34 }
35 return c
36}
37
38func main(){
39 var str1, str2 = []rune("Monday"), []rune("Friday")
40 fmt.Printf("Distance between Monday and Friday = %d\n", levenshtein(str1, str2)) // 3
41}
1function levenshtein(s, t) {
2 if(s.length === 0) return t.length;
3 if(t.length === 0) return s.length;
4 let m = new Array(s.length + 1).fill(0).map(
5 (_, i) => new Array(t.length + 1).fill(0).map(
6 (_,j) => i*j ? 0 : i+j
7 )
8 )
9 for(let i = 1; i <= s.length; i++) {
10 for(let j = 1; j <= t.length; j++) {
11 if(s[i - 1] === t[j - 1]) {
12 m[i][j] = m[i-1][j-1]
13 } else {
14 m[i][j] = Math.min(m[i - 1][j - 1], m[i - 1][j], m[i][j - 1]) + 1
15 }
16 }
17 }
18 return m[s.length][t.length]
19}
20
21console.log("Distance between Monday and Friday = %d\n", levenshtein("Monday", "Friday")); // 3
1fn levenshtein(word1: &str, word2: &str) -> usize {
2 let s = word1.chars().collect::<Vec<_>>();
3 let t = word2.chars().collect::<Vec<_>>();
4 let slength = s.len() + 1;
5 let tlength = t.len() + 1;
6 let mut m = vec![vec![0]];
7 for i in 1..slength { m[0].push(i); }
8 for j in 1..tlength { m.push(vec![j]); }
9
10 for j in 1..tlength {
11 for i in 1..slength {
12 let tmp: usize = if s[i-1] == t[j-1] {
13 m[j-1][i-1]
14 } else {
15 1 + std::cmp::min(
16 std::cmp::min(m[j][i-1], m[j-1][i])
17 , m[j-1][i-1])
18 };
19 m[j].push(tmp);
20 }
21 }
22 m[tlength-1][slength-1]
23}
24
25fn main() {
26 println!("{}", levenshtein("Monday", "Friday")); // 3
27}