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.33
1
Awgiedawgie 104555 points

                                    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

4.33 (3 Votes)
0
4.33
3
Lionel Aguero 7585 points

                                    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
}

4.33 (3 Votes)
0
4.5
4
Awgiedawgie 104555 points

                                    test 5

4.5 (2 Votes)
0
5
0
Rubixphys12 3705 points

                                    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
}

5 (1 Votes)
0
Are there any code examples left?
Made with love
This website uses cookies to make IQCode work for you. By using this site, you agree to our cookie policy

Pleased to see you again

Sign up to unlock all of IQCode features:
  • Master useful skills
  • Improve learning outcomes
  • Share your knowledge
Create an account
Sign in
Recover lost password
Or log in with

Create a Free Account

Sign up to unlock all of IQCode features:
  • Master useful skills
  • Improve learning outcomes
  • Share your knowledge
Create an account
Sign up
Or sign up with
By signing up, you agree to the Terms and Conditions and Privacy Policy. You also agree to receive product-related marketing emails from IQCode, which you can unsubscribe from at any time.
Creating a new code example
Code snippet title
Source