Задача: 583. Delete Operation for Two Strings
Сложность: 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 {
    function minDistance($word1, $word2) {
        $m = strlen($word1);
        $n = strlen($word2);
        $dp = array_fill(0, $n + 1, 0);

        for ($i = 0; $i <= $m; $i++) {
            $temp = array_fill(0, $n + 1, 0);
            for ($j = 0; $j <= $n; $j++) {
                if ($i == 0 || $j == 0) {
                    $temp[$j] = $i + $j;
                } else if ($word1[$i - 1] == $word2[$j - 1]) {
                    $temp[$j] = $dp[$j - 1];
                } else {
                    $temp[$j] = 1 + min($dp[$j], $temp[$j - 1]);
                }
            }
            $dp = $temp;
        }

        return $dp[$n];
    }
}

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