Levenshtein Distance Algorithm

levenshtein.scala

  // The straightforward, but very slow version
  def levenshteinDistance(a: String, b: String): Int = {
    val aLen = a.length
    val bLen = b.length
    def minimum(x: Int, y: Int, z: Int) = Math.min(Math.min(x, y), z)
    def max(i: String, j: String) = if (i >= j) i else j
    def min(i: String, j: String) = if (i <= j) i else j
    def cost = if (aLen - 1 == bLen - 1) 0 else 1

    if (min(a, b).length == 0) max(a, b).length
    else minimum(
      levenshteinDistance(a.dropRight(1), b) + 1,
      levenshteinDistance(a, b.dropRight(1)) + 1,
      levenshteinDistance(a.dropRight(1), b.dropRight(1)) + cost
    )
  }