Skip to content

Instantly share code, notes, and snippets.

@andre3k1
Created April 18, 2013 22:38
Show Gist options
  • Save andre3k1/5416791 to your computer and use it in GitHub Desktop.
Save andre3k1/5416791 to your computer and use it in GitHub Desktop.
Calculate the Levenshtein distance between two strings
package com.senzari
object Levenshtein {
def distance(start: String, target: String): Int = {
val slen = start.length()
val tlen = target.length()
def inner(start: String, target: String): Array[Array[Int]] = {
val slen = start.length()
val tlen = target.length()
var matrix = Array.ofDim[Int](slen+1, tlen+1)
var matrixCost = Array.ofDim[Int](slen, tlen)
for (i <- 0 to slen) matrix(i)(0) = i
for (j <- 0 to tlen) matrix(0)(j) = j
for (i <- 0 until slen ; j <- 0 until tlen) {
val (s, t) = (start(i), target(j))
val cost = if (s == t) 0 else 1
val costs = List(
matrix(i)(j+1) + 1,
matrix(i+1)(j) + 1,
matrix(i)(j) + cost)
val min = costs.reduceLeft(Math.min)
matrix(i+1)(j+1) = min;
}
return matrix
}
return inner(start, target)(slen)(tlen)
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment