583. Delete Operation for Two Strings

leetcode medium

#array#csharp#dynamic-programming#leetcode#math#medium#string

Task

Даны две строки 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".

C# solution

matched/original

public class Solution {
    public int MinDistance(string word1, string word2) {
        int m = word1.Length;
        int n = word2.Length;
        int[] dp = new int[n + 1];
        for (int i = 0; i <= m; i++) {
            int[] temp = new int[n + 1];
            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 + Math.Min(dp[j], temp[j - 1]);
                }
            }
            dp = temp;
        }
        return dp[n];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<int>& dp = new int[n + 1];
        for (int i = 0; i <= m; i++) {
            vector<int>& temp = new int[n + 1];
            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];
    }
}

Java solution

matched/original

public class Solution {
    public int minDistance(String s1, String s2) {
        int[] dp = new int[s2.length() + 1];
        for (int i = 0; i <= s1.length(); i++) {
            int[] temp=new int[s2.length()+1];
            for (int j = 0; j <= s2.length(); j++) {
                if (i == 0 || j == 0)
                    temp[j] = i + j;
                else if (s1.charAt(i - 1) == s2.charAt(j - 1))
                    temp[j] = dp[j - 1];
                else
                    temp[j] = 1 + Math.min(dp[j], temp[j - 1]);
            }
            dp=temp;
        }
        return dp[s2.length()];
    }
}

JavaScript solution

matched/original

var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length;
    let dp = new Array(n + 1).fill(0);

    for (let i = 0; i <= m; i++) {
        let temp = new Array(n + 1).fill(0);
        for (let 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 + Math.min(dp[j], temp[j - 1]);
            }
        }
        dp = temp;
    }

    return dp[n];
};

Python solution

matched/original

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [0] * (n + 1)

        for i in range(m + 1):
            temp = [0] * (n + 1)
            for j in range(n + 1):
                if i == 0 or j == 0:
                    temp[j] = i + j
                elif 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]

Go solution

matched/original

func minDistance(word1 string, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([]int, n+1)

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

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Explanation

Algorithm

Инициализация массива:

Создайте одномерный массив dp для хранения минимального количества удалений, необходимых для уравнивания строк word1 и word2.

Заполнение массива:

Используйте временный массив temp для обновления значений dp, представляющих текущую строку. Обновите temp с использованием значений dp предыдущей строки.

Обновление и результат:

Скопируйте временный массив temp обратно в dp после обработки каждой строки. В конце верните значение из dp, представляющее минимальное количество удалений.

😎