// https://leetcode.com/problems/edit-distance
fun minDistance(word1: String, word2: String): Int {
    return minDistance(word1, word2, 0, 0, Array(word1.length) { IntArray(word2.length) { -1 } })
}

private fun minDistance(word1: String, word2: String, index1: Int, index2: Int, memo: Array<IntArray>): Int {
    if (word1.length == index1) {
        return word2.length - index2
    }
    if (word2.length == index2) {
        return word1.length - index1
    }

    if (memo[index1][index2] != -1) {
        return memo[index1][index2]
    }

    memo[index1][index2] = if (word1[index1] == word2[index2]) {
        minDistance(word1, word2, index1 + 1, index2 + 1, memo)
    } else {
        val insert = minDistance(word1, word2, index1, index2 + 1, memo)
        val remove = minDistance(word1, word2, index1 + 1, index2, memo)
        val replace = minDistance(word1, word2, index1 + 1, index2 + 1, memo)
        1 + minOf(insert, remove, replace)
    }
    return memo[index1][index2]
}

// https://leetcode.com/problems/edit-distance
fun minDistance(word1: String, word2: String): Int {
    return minDistance(word1, word2, 0, 0, Array(word1.length) { IntArray(word2.length) { -1 } })
}

private fun minDistance(word1: String, word2: String, index1: Int, index2: Int, memo: Array<IntArray>): Int {
    if (word1.length == index1) {
        return word2.length - index2
    }
    if (word2.length == index2) {
        return word1.length - index1
    }

    if (memo[index1][index2] != -1) {
        return memo[index1][index2]
    }

    memo[index1][index2] = if (word1[index1] == word2[index2]) {
        minDistance(word1, word2, index1 + 1, index2 + 1, memo)
    } else {
        val insert = minDistance(word1, word2, index1, index2 + 1, memo)
        val remove = minDistance(word1, word2, index1 + 1, index2, memo)
        val replace = minDistance(word1, word2, index1 + 1, index2 + 1, memo)
        1 + minOf(insert, remove, replace)
    }
    return memo[index1][index2]
}
