Delete Operation For Two Strings - Leetcode Solution

Problem Statement:

Given two strings s1 and s2, return the minimum number of steps required to make s1 and s2 identical, where a step is defined as deleting a character from either string.

Example:

Input: s1 = "sea", s2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".

Solution:

To solve this problem, we will use dynamic programming approach in which we will create a table to store the number of steps required to make s1[i:] and s2[j:] identical. We will start from the end of both strings and initialize the table with the number of steps required to make empty string identical to the respective substring.

For each cell in the table, we will check the following conditions:

• If s1[i] == s2[j], we don't need to delete anything, so we can move to the next cell by setting dp[i][j] = dp[i+1][j+1].
• If s1[i] != s2[j], we need to delete one character either from s1 or s2, so we will take the minimum number of steps required to delete from both strings and add 1 to it. dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + 1.

Finally, the minimum number of steps required to make s1 and s2 identical will be stored in dp[0][0].

Python Code:

def minStepsToDelete(s1: str, s2: str) -> int: n1, n2 = len(s1), len(s2) dp = [[0] * (n2+1) for _ in range(n1+1)] for i in range(n1,-1,-1): for j in range(n2,-1,-1): if i == n1: dp[i][j] = n2 - j elif j == n2: dp[i][j] = n1 - i elif s1[i] == s2[j]: dp[i][j] = dp[i+1][j+1] else: dp[i][j] = min(dp[i+1][j], dp[i][j+1]) + 1 return dp[0][0]

Time Complexity: O(mn) where m and n are the lengths of s1 and s2 respectively.

Space Complexity: O(mn) to store the dp table.

1