Guest User

Untitled

a guest
Oct 20th, 2017
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.52 KB | None | 0 0
  1. import Math._
  2.  
  3. object EditDistance extends App {
  4.  
  5. def minimum(i1: Int, i2: Int, i3: Int) = min(min(i1, i2), i3)
  6.  
  7. def distance(str1: String, str2: String): Int = {
  8. val dist = Array.tabulate(str2.length + 1, str1.length + 1) { (i, j) => if (j == 0) i else if (i == 0) j else 0 }
  9.  
  10. for (j <- 1 to str2.length; i <- 1 to str1.length)
  11. dist(j)(i) = if (str2(j - 1) == str1(i - 1)) dist(j - 1)(i - 1)
  12.  
  13. else minimum(dist(j - 1)(i) + 1, dist(j)(i - 1) + 1, dist(j - 1)(i - 1) + 1)
  14.  
  15. dist(str2.length)(str1.length)
  16. }
  17. }
Add Comment
Please, Sign In to add comment