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.
1using System;
2
3class Program {
4 public static int MinDistance(string word1, string word2) {
5 int m = word1.Length;
6 int n = word2.Length;
7 int[,] dp = new int[m + 1, n + 1];
8 for (int i = 1; i <= m; i++) {
9 for (int j = 1; j <= n; j++) {
10 if (word1[i - 1] == word2[j - 1]) {
11 dp[i, j] = dp[i - 1, j - 1] + 1;
12 } else {
dp[i, j] = Math.Max(dp[i - 1, j], dp[i, j - 1]);
}
}
}
return m + n - 2 * dp[m, n];
}
static void Main() {
string word1 = "sea";
string word2 = "eat";
Console.WriteLine(MinDistance(word1, word2));
}
}
This C# solution leverages a two-dimensional array created based on string lengths, updating it as we compute the LCS between the given words via sequential comparison. Similar to other language implementations, the result calculation stems from total length adjustment using the LCS-derived count.