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]
4
5
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
Thank you!
5
0
4.2
4
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
}
Thank you!
4
0
4.09
10
test 5
Thank you!
10
0
4
1
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
}
Thank you!
1
0
Are there any code examples left?
New code examples in category Rust
-
Rust 2022-03-28 00:00:04 rust print i8
-
Rust 2022-03-27 16:15:02 rust check if key in hashmap
-
Rust 2022-03-22 14:45:18 rust convert a string (with decimals) to a floating point number.
-
Rust 2022-03-11 21:00:15 creating constants in rust
-
Rust 2022-03-07 02:55:02 hello world in rust
-
Rust 2022-02-24 13:40:24 execution duration
-
Rust 2022-02-20 06:45:02 matching in rust
-
Rust 2022-02-19 18:35:12 rust bitset stack
-
Rust 2022-01-30 19:30:40 rust compile and run