Fewest Deletions to Match Two Words
Problem
Given two words a and b, one step deletes a single character from either word. Return the fewest steps needed to make the two words identical.
Examples
Input: a = "sea", b = "eat"
Output: 2
Why: delete the s from sea and the t from eat, leaving ea in bothInput: a = "abcde", b = "ace"
Output: 2
Why: ace already appears inside abcde in order, so only b and d goInput: a = "abc", b = ""
Output: 3
Why: edge case, everything in the first word must be deletedHints
0 / 3
Whatever is left after the deletions appears in both words, in the same order. What is the most you could keep?
The characters you keep form a common subsequence of the two words. Keeping the longest common subsequence means deleting as little as possible.
Compute the longest common subsequence length with a table where entry (i, j) covers the first i characters of a and the first j of b. The answer is len(a) + len(b) minus twice that length.
Solution
Deleting until the words match leaves a string that is a subsequence of both, so the fewest deletions come from keeping the longest common subsequence and removing everything else from each word. The table entry for the first i characters of a and the first j of b extends the diagonal entry by one when the last characters match, and otherwise takes the better of dropping the last character of either word. Every character outside the common subsequence is deleted once, which gives len(a) + len(b) - 2 * lcs. Time is O(m · n) and space is O(m · n) for words of lengths m and n.
def min_deletions(a, b):
m, n = len(a), len(b)
lcs = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
lcs[i][j] = lcs[i - 1][j - 1] + 1 # keep the matching pair
else:
lcs[i][j] = max(lcs[i - 1][j], lcs[i][j - 1])
return m + n - 2 * lcs[m][n] # delete everything not kept
print(min_deletions("sea", "eat")) # -> 2
print(min_deletions("abcde", "ace")) # -> 2
print(min_deletions("abc", "")) # -> 3Stuck on the idea rather than the code? Longest Common Subsequence covers it.