Задача: 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 {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int> dp(n + 1, 0);

        for (int i = 0; i <= m; ++i) {
            vector<int> temp(n + 1, 0);
            for (int 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];
    }
};

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