583. Delete Operation for Two Strings

Problem Statement Given two strings word1 and word2, determine the minimum number of steps required to make both strings identical, where each step allows you to delete exactly one character from either string.

Solution Approach This problem can be efficiently solved using dynamic programming. The key insight is that making strings equal through deletions is equivalent to finding the Longest Common Subsequence (LCS) and calculating how many characters need to be removed.

Define dp[i][j] as the minimum number of deletions needed to make the first i characters of word1 equal to the first j characters of word2.

Implementation

int minDistance(char* word1, char* word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[501][501];  // assuming max length constraint
    
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + fmin(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    
    return dp[len1][len2];
}

State Transition Logic

If current characters match: dp[i][j] = dp[i-1][j-1] (no deletion needed) If characters differ: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1]) (delete from either string)

72. Edit Distance

Problem Statement Given two strings word1 and word2, calculate the minimum number of operations required to convert word1 into word2. The allowed operations are:

Insert a chaarcter Delete a character Replace a character

Solution Approach This extends the deletion-only problem by including insertion and replacement operations. We use the same DP framework but with an additional operation to consider.

Define dp[i][j] as the minimum operations needed to convert the first i characters of word1 to the first j characters of word2.

Implementation

int minDistance(char* word1, char* word2) {
    int len1 = strlen(word1);
    int len2 = strlen(word2);
    int dp[501][501];
    
    for (int i = 0; i <= len1; i++) {
        dp[i][0] = i;
    }
    for (int j = 0; j <= len2; j++) {
        dp[0][j] = j;
    }
    
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                int deleteOp = dp[i - 1][j];
                int insertOp = dp[i][j - 1];
                int replaceOp = dp[i - 1][j - 1];
                dp[i][j] = 1 + fmin(deleteOp, fmin(insertOp, replaceOp));
            }
        }
    }
    
    return dp[len1][len2];
}

State Transition Logic

If current characters match: dp[i][j] = dp[i-1][j-1] (no operation needed) If characters differ: dp[i][j] = 1 + min(delete, insert, replace) operations

Complexity Analysis Both solutions have a time complexity of O(mn) and space complexity of O(mn), where m and n are the lengths of the two input strings.

Relationship Between Problems Problem 583 is a special case of Problem 72 where only deletion operations are permitted. The edit distance problem generalizes this by adding insertion and replacement capabilities, making it more versatile for applications like spell checking, DNA sequence alignment, and diff tools.