Delete Operation for Two Strings
Problem
Given two strings word1 and word2, return the minimum number of single-character deletions required to make the two strings equal.
word1 = "sea", word2 = "eat"2def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0]*(n + 1) for _ in range(m + 1)]
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])
lcs = dp[m][n]
return (m - lcs) + (n - lcs)function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
const lcs = dp[m][n];
return (m - lcs) + (n - lcs);
}class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length(), n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1))
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
int lcs = dp[m][n];
return (m - lcs) + (n - lcs);
}
}int minDistance(string word1, string word2) {
int m = word1.size(), n = word2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
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]);
}
}
int lcs = dp[m][n];
return (m - lcs) + (n - lcs);
}Explanation
To make two words equal using only deletions, the characters you keep must be identical in both — and in the same order. That kept part is exactly the longest common subsequence (LCS). Everything outside the LCS must be deleted.
So the plan is: find the LCS length, then delete whatever is left over in each word. If the LCS has length lcs, you delete (m - lcs) chars from word1 and (n - lcs) from word2.
We compute the LCS with a 2D table where dp[i][j] is the LCS of the first i chars of word1 and first j of word2. If the current characters match, dp[i][j] = dp[i-1][j-1] + 1; otherwise we carry over the best of dropping one character: max(dp[i-1][j], dp[i][j-1]).
Example: word1 = "sea", word2 = "eat". The LCS is "ea" with length 2. Deletions are (3 - 2) + (3 - 2) = 2 (drop the 's' from "sea" and the 't' from "eat").
Filling the table touches every (i, j) pair once, so the work is proportional to m · n.