Levenshtein Kotlin Implementation

levenshtein.kt

package madu.ezsug

import kotlin.math.min

fun calcDistance(source: String, target: String): Int {
    println("(Source: $source) -> (Target: $target)")

    val rowCount = target.length + 1 // add one for empty string
    val columnCount = source.length + 1 // // add one for empty string

    // initialize the 0th row
    var prevRow = initialRow(columnCount)

    printHeader(source)
    printRow(prevRow)

    for (i in 1 until rowCount) {
        prevRow = buildRow(i, prevRow, columnCount, source, target)
        printRow(prevRow, target[i - 1])
    }

    return prevRow[columnCount-1]
}

fun buildRow(rowIndex: Int, prevRow: Array<Int>, columnCount: Int, source: String, target: String): Array<Int> {
    val currentRow = emptyRow(columnCount)
    val letter = target[rowIndex - 1]

    // First column is always current row
    currentRow[0] = rowIndex

    for (colIndex in 1 until columnCount) {
        val deletionCost = prevRow[colIndex] + 1
        val insertionCost = currentRow[colIndex - 1] + 1

        val replaceCost = when(source[colIndex - 1] != letter) {
            true -> prevRow[colIndex - 1] + 1
            false -> prevRow[colIndex - 1]
        }

        currentRow[colIndex] = min(min(deletionCost, insertionCost), replaceCost)
    }

    return currentRow
}

fun emptyRow(columnCount: Int): Array<Int> {
    return Array(columnCount) { 0 }
}

fun initialRow(columnCount: Int): Array<Int> {
    val arr = emptyRow(columnCount)

    for (i in 0 until columnCount) {
        arr[i] = i
    }

    return arr
}

fun printHeader(word: String) {
    val paddedWord = ' ' + word
    val prettyWord = paddedWord.split("").joinToString("|", " ", " ")

    println(prettyWord)
}

fun printRow(row: Array<Int>, letter: Char = ' ') {
    val prettyStr = row.joinToString("|", "|", "|")

    println(letter + prettyStr)
}