EditDistance.scala

EditDistance.scala

def editDistance(s1: String, s2: String): Int = {

  val s1Arr = s1.toCharArray
  val s2Arr = s2.toCharArray

  val mapOfEditDistance = scala.collection.mutable.HashMap.empty[(Int, Int), Int]

  def editDistanceHelperDP(i: Int, j: Int): Int = {
    mapOfEditDistance.getOrElseUpdate((i, j), if(i == -1) {
      mapOfEditDistance.update((i, j), j + 1)
      j + 1
    }
    else if(j == -1) {
      mapOfEditDistance.update((i, j), i + 1)
      i + 1
    }
    else {
      if(s1Arr(i) == s2Arr(j)) {
        mapOfEditDistance.getOrElseUpdate((i-1, j-1), editDistanceHelperDP(i - 1, j - 1))
      } else {
        val f1 = mapOfEditDistance.getOrElseUpdate((i, j-1), editDistanceHelperDP(i, j - 1) + 1)
        val f2 = mapOfEditDistance.getOrElseUpdate((i-1, j), editDistanceHelperDP(i - 1, j) + 1)
        val f3 = mapOfEditDistance.getOrElseUpdate((i-1, j-1), editDistanceHelperDP(i-1, j-1) + 1)
        math.min(f3, math.min(f1, f2))
      }
    })
  }
  editDistanceHelperDP(s1.length - 1, s2.length - 1)
}