Sponsored
Sponsored
This approach is based on finding the Longest Common Subsequence (LCS) between the two given strings. Once we have the LCS, the number of deletions needed is the sum of the lengths of the two strings minus twice the length of the LCS. The LCS represents the longest sequence that both strings have in common without rearranging their order. The deletions from either string will only be those characters not present in the LCS.
Here's a step-by-step process to solve the problem:
dp where dp[i][j] represents the length of LCS of string word1[0...i] and word2[0...j].dp array using the recurrence: if word1[i-1] == word2[j-1], then dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).len(word1) + len(word2) - 2 * dp[len(word1)][len(word2)].Time Complexity: O(m * n), where m and n are the lengths of the two strings.
Space Complexity: O(m * n), as a 2D table is used for storing intermediate results.
1public class Solution {
2 public int minDistance(String word1, String word2) {
3 int m = word1.length(
The Java solution follows the DP approach to determine the LCS length. It initializes a two-dimensional array and fills it according to the LCS formula described. At the end, the total operations required are derived by computing the difference between the total string lengths and twice the LCS.