Сложность: medium
Даны две строки word1 и word2, вернуть минимальное количество шагов, необходимых для того, чтобы сделать word1 и word2 одинаковыми.
На одном шаге можно удалить ровно один символ в любой строке.
Пример:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
👨💻 Алгоритм:
1⃣ Инициализация массива:
Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.
2⃣ Заполнение массива:
Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.
3⃣ Обновление и результат:
Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.
😎 Решение:
class Solution {
func minDistance(_ word1: String, _ word2: String) -> Int {
let m = word1.count, n = word2.count
var dp = [Int](repeating: 0, count: n + 1)
let s1 = Array(word1), s2 = Array(word2)
for i in 0...m {
var temp = [Int](repeating: 0, count: n + 1)
for j in 0...n {
if i == 0 || j == 0 {
temp[j] = i + j
} else if s1[i - 1] == s2[j - 1] {
temp[j] = dp[j - 1]
} else {
temp[j] = 1 + min(dp[j], temp[j - 1])
}
}
dp = temp
}
return dp[n]
}
}Ставь 👍 и забирай 📚 Базу знаний