Last updated on January 10th, 2025 at 12:19 am

Here, we see a Delete Operation for Two Strings LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Companies

Google

Level of Question

Medium

Delete Operation for Two Strings LeetCode Solution

1. 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

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “Longest Common Subsequence (LCS)”, which is a Dynamic Programming (DP) problem. The code calculates the minimum number of operations (insertions and deletions) required to make two strings identical by leveraging the LCS concept.

3. Code Implementation in Different Languages

3.1 Delete Operation for Two Strings 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];
    }
};

3.2 Delete Operation for Two Strings 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.3 Delete Operation for Two Strings 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] 
};

3.4 Delete Operation for Two Strings 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]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	(O(m * n))	(O(m * n))
Java	(O(m * n))	(O(n))
JavaScript	(O(m * n))	(O(n))
Python	(O(m * n))	(O(n))

Here, m is the length of word1, and n is the length of word2.