Levenshtein Distance

levenshtein.kt

fun main() {
    val word1 = "kitten"
    val word2 = "sitting"
    val distance = levenshteinDistanceOp(word1, word2)
    println("Levenshtein distance between $word1 and $word2 is $distance")
    
    val input = "kotln"
    val target = "kotlin"
    val tolerance = 1 // Allow up to 1 typo

    println("Is fuzzy match: ${isFuzzyMatch(input, target, tolerance)}")
    println("Levenshtein distance between $input and $target is ${levenshteinDistanceOp(input, target)}")
}

// Code review comment -> Consider renaming the function to reflect its purpose more clearly.
fun isFuzzyMatch(input: String, target: String, tolerance: Int): Boolean {
    // Code review comment -> Add validation for null or empty inputs.
    val distance = levenshteinDistance(input, target)
    return distance <= tolerance
}

// Code review comment -> Optimize the space complexity by using only one array.
fun levenshteinDistance(lhs: CharSequence, rhs: CharSequence): Int {
    if (lhs == rhs) {
        return 0
    }
    if (lhs.isEmpty()) {
        return rhs.length
    }
    if (rhs.isEmpty()) {
        return lhs.length
    }

    val len0 = lhs.length + 1
    val len1 = rhs.length + 1

    var cost = Array(len0) { it }
    var newCost = Array(len0) { 0 }

    for (i in 1 until len1) {
        newCost[0] = i

        for (j in 1 until len0) {
            val match = if (lhs[j - 1] == rhs[i - 1]) 0 else 1

            val costReplace = cost[j - 1] + match
            val costInsert = cost[j] + 1
            val costDelete = newCost[j - 1] + 1

            newCost[j] = minOf(costInsert, costDelete, costReplace)
        }

        val swap = cost
        cost = newCost
        newCost = swap
    }

    return cost[len0 - 1]
}


fun levenshteinDistanceOp(s1: String, s2: String): Int {
    val dp = IntArray(s2.length + 1) { 0 }
    
//     Initialise first row
    for (i in 0..s2.length) {
        dp[i] = i
    }
    
//     Fill in the rest of the array
	for (i in 1..s1.length) {
        var prev = dp[0]
        dp[0] = i
        
        for (j in 1..s2.length) {
            val temp = dp[j]
            if (s1[i - 1] == s2[j - 1]) {
                dp[j] = prev
            } else {
                dp[j] = minOf(dp[j - 1], dp[j], prev) + 1
            }
            prev = temp
        }
    }
    return dp.last()
}