levdist <- function(s,t) {
    s <- strsplit(s,'')[[1]]
    t <- strsplit(t,'')[[1]]

    n <- length(s)
    m <- length(t)

    if (n == 0) {
        return (m)
    } else if (m == 0) {
        return (n)
    }


    d <- matrix(0,nrow=m+1, ncol=n+1)
    d[1,] <- 0:n
    d[,1] <- 0:m

    for (i in 2:(n+1)) {
        for (j in 2:(m+1)) {

            cost = 1
            
            if (s[i-1] == t[j-1]) {
                cost = 0
            } else {
                cost = 1
            }

            d[j,i] = min(c(d[j-1,i]+1,d[j,i-1]+1,d[j-1,i-1]+cost))
        }
    }
    return(d[m+1,n+1])
}