leetcode: 583. Delete Operation for Two Strings

problem

• https://leetcode.com/problems/delete-operation-for-two-strings/

O(NM) time

• N: length of word1
• M: length of word2

class Solution {
    fun minDistance(word1: String, word2: String): Int {
        val len1 = word1.length
        val len2 = word2.length
        // dp[i][j] means longest common sequence between word1[:i] and word2[:j]
        val dp = Array(len1 + 1) { IntArray(len2 + 1) { 0 }}
        for (i in 1..len1) {
            for (j in 1..len2) {                
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1            
                } else {
                    dp[i][j] = maxOf(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        return len1 - dp[len1][len2] + len2 - dp[len1][len2]
    }
}