Задача: 712. Minimum ASCII Delete Sum for Two Strings
Сложность: medium

Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.

Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.

2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки.

3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).

😎 Решение:

func minimumDeleteSum(_ s1: String, _ s2: String) -> Int {
    let s1Array = Array(s1)
    let s2Array = Array(s2)
    var dp = Array(repeating: Array(repeating: 0, count: s2Array.count + 1), count: s1Array.count + 1)
    for i in 1...s1Array.count {
        dp[i][0] = dp[i - 1][0] + Int(s1Array[i - 1].asciiValue!)
    }
    for j in 1...s2Array.count {
        dp[0][j] = dp[0][j - 1] + Int(s2Array[j - 1].asciiValue!)
    }
    for i in 1...s1Array.count {
        for j in 1...s2Array.count {
            if s1Array[i - 1] == s2Array[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = min(dp[i - 1][j] + Int(s1Array[i - 1].asciiValue!), dp[i][j - 1] + Int(s2Array[j - 1].asciiValue!))
            }
        }
    }
    return dp[s1Array.count][s2Array.count]
}

Ставь 👍 и забирай 📚 Базу знаний