Задача: 712. Minimum ASCII Delete Sum for Two Strings
Если даны две строки 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])).
😎 Решение:
fun minimumDeleteSum(s1: String, s2: String): Int {
val dp = Array(s1.length + 1) { IntArray(s2.length + 1) }
for (i in 1..s1.length) {
dp[i][0] = dp[i - 1][0] + s1[i - 1].toInt()
}
for (j in 1..s2.length) {
dp[0][j] = dp[0][j - 1] + s2[j - 1].toInt()
}
for (i in 1..s1.length) {
for (j in 1..s2.length) {
if (s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]
} else {
dp[i][j] = minOf(dp[i - 1][j] + s1[i - 1].toInt(), dp[i][j - 1] + s2[j - 1].toInt())
}
}
}
return dp[s1.length][s2.length]
}👉Новости 👉База вопросов