We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete Operation for Two Strings

Number: 583

Difficulty: Medium

Paid? No

Companies: Google, ByteDance

Problem Description

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

Key Insights

  • The problem can be transformed to finding the longest common subsequence (LCS) between the two strings.
  • The minimum number of deletion steps equals the sum of the lengths of the two strings minus twice the length of their LCS.
  • Dynamic Programming is employed to efficiently compute the LCS.

Space and Time Complexity

Time Complexity: O(m * n), where m and n are the lengths of word1 and word2 respectively. Space Complexity: O(m * n), due to the use of a 2D DP table.

Solution

We use a Dynamic Programming approach to determine the longest common subsequence (LCS) of the two strings. First, we construct a 2D DP table where dp[i][j] represents the length of the LCS for word1[0:i] and word2[0:j]. The recurrence is defined as follows:

  • If the characters at positions i-1 in word1 and j-1 in word2 match, then dp[i][j] = dp[i-1][j-1] + 1.
  • Otherwise, dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Once the LCS is computed, the minimum deletions can be calculated by subtracting twice the LCS length from the sum of the lengths of the two strings.

Code Solutions

# Function to compute minimum deletion steps to make two strings identical
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    # Create a 2D DP table with dimensions (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Build the DP table bottom-up
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            # If current characters match, increase length by 1 from previous diagonal cell
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                # Otherwise, take the maximum from the left or top adjacent cell
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    # The LCS length is stored at dp[m][n]
    lcs_length = dp[m][n]
    # Calculate and return the minimum number of deletion steps
    return (m - lcs_length) + (n - lcs_length)

# Example usage
print(minDistance("sea", "eat"))
← Back to All Questions