LevenshteinDistance.scala

object LevenshteinDistance {
  private def editDistance(str1: String, str2: String): Int = {
    val cols: Int = str1.length
    val rows: Int = str2.length
    val chars1: Array[Char] = str1.toCharArray
    val chars2: Array[Char] = str2.toCharArray
    val dp = new Array[Array[Int]](rows + 1).map(ys => new Array[Int](cols + 1))

    for (row <- 0 to rows) {
      dp(row)(0) = row
    }
    for (col <- 0 to cols) {
      dp(0)(col) = col
    }

    for (i <- 1 to rows) {
      for (j <- 1 to cols) {
        val leftCost = dp(i)(j-1) + 1
        val upperCost = dp(i-1)(j) + 1
        val diagonalCost = if (chars1(j-1) == chars2(i-1)) {
          dp(i-1)(j-1)
        } else {
          dp(i-1)(j-1) + 1
        }
        dp(i)(j) = List(leftCost, upperCost, diagonalCost).min
      }
    }
    dp(rows)(cols)
  }
}