levenshtein in scala

gistfile1.scala

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package scalaapplication1

object Main {

  def lv2(s1:String, s2:String, n1:Int, n2:Int):Int = {
    (n1, n2) match{
      case (i, 0) => i
      case (0, j) => j
      case _ => List(lv2(s1, s2, n1 - 1, n2) + 1,
                     lv2(s1, s2, n1, n2 - 1) + 1,
                     lv2(s1, s2, n1 - 1, n2 - 1) + (if(s1(n1 - 1) == s2(n2 - 1)) 0 else 1)
                ).min

    }
  }
  /**
   * recursive version
   */
  def levenshtein2(s1:String, s2:String):Int = lv2(s1, s2, s1.length, s2.length)
  /**
   * 
   */
  def levenshtein(str1:String, str2:String):Int = {
    val m = new Array[Array[Int]](str1.length + 1)
    for(i <- 0 to str1.length) m(i) = new Array[Int](str2.length + 1)
    for(i <- 0 to str1.length) m(i)(0) = i
    for(j <- 0 to str2.length) m(0)(j) = j
    for(i <- 1 to str1.length; j <- 1 to str2.length) {
      val x = if(str1(i - 1) == str2(j - 1))
        0
      else
        1
      m(i)(j) = List(m(i - 1)(j) + 1, m(i)(j - 1) + 1, m(i - 1)(j - 1) + x).min
    }
    m(str1.length)(str2.length)
  }
  /**
   * @param args the command line arguments
   */
  def main(args: Array[String]): Unit = {
    val s = "abc"
    
    println(levenshtein2("kitten", "sitting"))
  }

}