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]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")); // 3levenshtein 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
}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
}Copyright © 2021 Codeinu
Forgot your account's password or having trouble logging into your Account? Don't worry, we'll help you to get back your account. Enter your email address and we'll send you a recovery link to reset your password. If you are experiencing problems resetting your password contact us
