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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete Operation for Two Strings

Difficulty: Medium

Problem Description

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.

Key Insights

  • The problem can be reduced to finding the longest common subsequence (LCS) between the two strings.
  • The minimum number of deletions required to make the strings identical is the sum of the lengths of both strings minus twice the length of the LCS.
  • Dynamic programming is a suitable approach 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) for the DP table used to store the lengths of LCS.

Solution

The solution uses dynamic programming to find the longest common subsequence (LCS) of the two strings. A 2D array dp is created where dp[i][j] represents the length of LCS of the first i characters of word1 and the first j characters of word2. If the characters match, the value is derived from the diagonal cell plus one; otherwise, it's the maximum of the left or top cell. Finally, the minimum deletions required are calculated using the formula: (length of word1 + length of word2 - 2 * LCS length).

Code Solutions

def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    # Create a DP table with size (m+1) x (n+1)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    
    # Length of the longest common subsequence
    lcs_length = dp[m][n]
    # Minimum deletions required
    return (m + n - 2 * lcs_length)
← Back to All Questions