Last updated on October 5th, 2024 at 03:56 pm

Here, We see Delete Operation for Two Strings LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Delete Operation for Two Strings LeetCode Solution

Problem Statement

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.

In one step, you can delete exactly one character in either string.

Example 1:
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”.

Example 2:
Input: word1 = “leetcode”, word2 = “etco”
Output: 4

1. Delete Operation for Two Strings Leetcode Solution C++

class Solution {
public:
    int minDistance(string word1, string word2) 
    {
        int m=word1.length(), n=word2.length(); 
        vector<vector<int>> dp(m+1, vector<int> (n+1, 0)); 
        for(int i=0; i<=m; i++)
        {
            for(int j=0; j<=n; j++)
            {
                if(i==0 || j==0) continue;
                else if(word1[i-1]==word2[j-1])
                    dp[i][j] = 1+dp[i-1][j-1];
                else
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return m+n-2*dp[m][n];
    }
};

2. Delete Operation for Two Strings Leetcode Solution Java

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length(), n = word2.length();
        if (m < n) {
            String tempStr = word1;
            word1 = word2;
            word2 = tempStr;
            int tempInt = n;
            n = m;
            m = tempInt;
        }
        char[] WA1 = word1.toCharArray(), WA2 = word2.toCharArray();
        int[] dpLast = new int[n+1], dpCurr = new int[n+1];
        for (char c1 : WA1) {
            for (int j = 0; j < n; j++) 
                dpCurr[j+1] = c1 == WA2[j]
                    ? dpLast[j] + 1
                    : Math.max(dpCurr[j], dpLast[j+1]);
            int[] tempArr = dpLast;
            dpLast = dpCurr;
            dpCurr = tempArr;
        }
        return m + n - 2 * dpLast[n];
    }
}

3. Delete Operation for Two Strings Leetcode Solution JavaScript

var minDistance = function(word1, word2) {
    let m = word1.length, n = word2.length
    if (m < n) [word1, word2, m, n] = [word2, word1, n, m]
    let WA1 = word1.split(""), WA2 = word2.split(""),
        dpLast = new Uint16Array(n + 1),
        dpCurr = new Uint16Array(n + 1)
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) 
            dpCurr[j+1] = WA1[i] === WA2[j]
                ? dpLast[j] + 1
                : Math.max(dpCurr[j], dpLast[j+1]);
        [dpLast, dpCurr] = [dpCurr, dpLast]
    }
    return m + n - 2 * dpLast[n] 
};

4. Delete Operation for Two Strings Leetcode Solution Python

class Solution(object):
    def minDistance(self, word1, word2):
        m, n = len(word1), len(word2)
        if m < n: word1, word2, m, n = word2, word1, n, m
        dpLast, dpCurr = [0] * (n + 1), [0] * (n + 1)
        for c1 in word1:
            for j in range(n):
                dpCurr[j+1] = dpLast[j] + 1 if c1 == word2[j] else max(dpCurr[j], dpLast[j+1])
            dpLast, dpCurr = dpCurr, dpLast
        return m + n - 2 * dpLast[n]