algoadvance

Leetcode 583. Delete Operation for Two Strings

Problem Statement

You are given two strings word1 and word2. Your task is to 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

Clarifying Questions

1. Can the strings contain any characters other than lowercase English letters?
   • No, you can assume that the strings only contain lowercase English letters.
2. What is the length range of word1 and word2?
   • Both word1 and word2 have lengths that range from 1 to 500.
3. Do we need to consider cases where input strings might be empty?
   • Yes, but the constraints ensure that the strings length from 1 to 500, so an empty string won’t be a part of typical test cases.

Strategy

To solve this problem, we can use Dynamic Programming to find the longest common subsequence (LCS) of word1 and word2. The idea is to find the longest sequence that appears in both strings without reordering characters. Once we have the length of this sequence, we can determine the minimum deletions needed to make the strings equal by calculating:

[ \text{deletions} = (\text{length of } word1 - \text{LCS}) + (\text{length of } word2 - \text{LCS}) ]

This is because any character that is not part of the LCS must be deleted.

Code

public class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();

        // Create a DP table to store lengths of longest common subsequence.
        int[][] dp = new int[m + 1][n + 1];

        // Build the dp table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // Length of longest common subsequence
        int lcsLength = dp[m][n];

        // The answer is the total number of characters minus twice the lcsLength.
        return (m - lcsLength) + (n - lcsLength);
    }
}

Time Complexity

• Time Complexity: The time complexity of this approach is (O(m \cdot n)), where (m) is the length of word1 and (n) is the length of word2. This is because we use nested loops to fill in the DP table with dimensions ( (m+1) \times (n+1) ).

• Space Complexity: The space complexity is ( O(m \cdot n) ) as we are using a 2D array of size ( (m+1) \times (n+1) ) to store the DP values.

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

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?