algoadvance

Leetcode 583. Delete Operation for Two Strings

Problem Statement

Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same. In each step, you can delete one character in either string.

Clarifying Questions

  1. What is the maximum length of the strings?
    • This information can help in evaluating the feasibility of different solutions, especially for dynamic programming approaches.
    • Assume the length of each string can be up to 500 for this problem.
  2. Are the characters case-sensitive?
    • Yes, all characters are considered case-sensitive, so ‘a’ and ‘A’ are different characters.
  3. What should be done if one or both of the strings are empty?
    • If one string is empty and the other is not, the number of steps is the length of the non-empty string, because you will need to delete all its characters to make it the same as an empty string.

Strategy

To solve this problem, we can use dynamic programming. The key idea is to determine the minimum number of deletions required by finding the length of the Longest Common Subsequence (LCS) of the two strings. Here’s the step-by-step approach:

  1. Compute the LCS of the two strings.
    • If we know the LCS, then the number of deletions needed for word1 is word1.length() - LCS_length and for word2 it’s word2.length() - LCS_length.
  2. Formulate the DP table to find the LCS:
    • dp[i][j] would represent the length of LCS of the substrings word1[0:i] and word2[0:j].
  3. Fill the DP table using the following rules:
    • If word1[i] == word2[j], then dp[i][j] = dp[i-1][j-1] + 1.
    • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).
  4. Calculate the minimum deletes required:
    • min_deletions = (len(word1) - LCS_length) + (len(word2) - LCS_length).

Code

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int minDistance(string word1, string word2) {
    int m = word1.size();
    int n = word2.size();
    
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    
    // Fill the dp table
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    int lcs_length = dp[m][n];
    int min_deletions = (m - lcs_length) + (n - lcs_length);
    return min_deletions;
}

// Test cases
int main() {
    string word1 = "sea";
    string word2 = "eat";
    cout << "Minimum deletions to make 'sea' and 'eat' the same: " << minDistance(word1, word2) << endl;
    
    word1 = "leetcode";
    word2 = "etco";
    cout << "Minimum deletions to make 'leetcode' and 'etco' the same: " << minDistance(word1, word2) << endl;

    return 0;
}

Time Complexity

The time and space complexity for this solution is:

This dynamic programming approach ensures that we compute the solution efficiently within these constraints.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI