Skip to content

Instantly share code, notes, and snippets.

@Samuel-William
Forked from tixxit/EditDistance.scala
Created April 29, 2020 02:14
Show Gist options
  • Save Samuel-William/c8e20a8a15800913a35a741aa400bf3c to your computer and use it in GitHub Desktop.
Save Samuel-William/c8e20a8a15800913a35a741aa400bf3c to your computer and use it in GitHub Desktop.
Short Levenshtein distance implementation in Scala
package net.tixxit.levenshtein
import scala.math.min
object EditDistance {
def editDist[A](a: Iterable[A], b: Iterable[A]) =
((0 to b.size).toList /: a)((prev, x) =>
(prev zip prev.tail zip b).scanLeft(prev.head + 1) {
case (h, ((d, v), y)) => min(min(h + 1, v + 1), d + (if (x == y) 0 else 1))
}) last
}
@Samuel-William
Copy link
Author

Usage:
println(editDist("sam","sam"))

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment