583. Delete Operation for Two Strings LeetCode Solution

In this guide, you will get 583. Delete Operation for Two Strings LeetCode Solution with the best time and space complexity. The solution to Delete Operation for Two Strings problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Delete Operation for Two Strings solution in C++
Delete Operation for Two Strings solution in Java
Delete Operation for Two Strings solution in Python
Additional Resources

583. Delete Operation for Two Strings LeetCode Solution image

Problem Statement of Delete Operation for Two Strings

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

Constraints:

1 <= word1.length, word2.length <= 500
word1 and word2 consist of only lowercase English letters.

Complexity Analysis

Time Complexity: O(mn)
Space Complexity: O(mn)

583. Delete Operation for Two Strings LeetCode Solution in C++

class Solution {
 public:
  int minDistance(string word1, string word2) {
    const int k = lcs(word1, word2);
    return (word1.length() - k) + (word2.length() - k);
  }

 private:
  int lcs(const string& a, const string& b) {
    const int m = a.length();
    const int n = b.length();
    // dp[i][j] := the length of LCS(a[0..i), b[0..j))
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (a[i - 1] == b[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 dp[m][n];
  }
};
/* code provided by PROGIEZ */

583. Delete Operation for Two Strings LeetCode Solution in Java

class Solution {
  public int minDistance(String word1, String word2) {
    final int k = lcs(word1, word2);
    return (word1.length() - k) + (word2.length() - k);
  }

  private int lcs(final String a, final String b) {
    final int m = a.length();
    final int n = b.length();
    // dp[i][j] := the length of LCS(a[0..i), b[0..j))
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; ++i)
      for (int j = 1; j <= n; ++j)
        if (a.charAt(i - 1) == b.charAt(j - 1))
          dp[i][j] = 1 + dp[i - 1][j - 1];
        else
          dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);

    return dp[m][n];
  }
}
// code provided by PROGIEZ

583. Delete Operation for Two Strings LeetCode Solution in Python

class Solution:
  def minDistance(self, word1: str, word2: str) -> int:
    k = self._lcs(word1, word2)
    return (len(word1) - k) + (len(word2) - k)

  def _lcs(self, a: str, b: str) -> int:
    m = len(a)
    n = len(b)
    # dp[i][j] := the length of LCS(a[0..i), b[0..j))
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
      for j in range(1, n + 1):
        if a[i - 1] == b[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 dp[m][n]
 # code by PROGIEZ