On the Internet, I recently came across an interesting task. I share with you its solution.
Task Description
Task Description
Given two strings of uppercase letters
source and target, list (in string form) a sequence of edits to convert from source to targetthat uses the least edits possible.
For example, with strings
source = "ABCDEFG", and target = "ABDFFGH" we might return: ["A", "B", "-C", "D", "-E", "F", "+F", "G", "+H"
More formally, for each character
C in source, we will either write the token C, which does not count as an edit; or write the token -C, which counts as an edit.
Additionally, between any token that we write, we may write
+Dwhere D is any letter, which counts as an edit.
At the end, when reading the tokens from left to right, and not including tokens prefixed with a minus-sign, the letters should spell out
target (when ignoring plus-signs.)
In the example, the answer of
A B -C D -E F +F G +H has total number of edits 4 (the minimum possible), and ignoring subtraction-tokens, spells out A, B, D, F, +F, G, +H which represents the string target.
If there are multiple answers, use the answer that favors removing from the source first.
Constraints:
- [time limit] 5000ms
- [input] string
source- 2 ≤ source.length ≤ 12
- [input] string
target- 2 ≤ target.length ≤ 12
- [output] array.string
Solution: Dynamic Programming + Construction
Our solution will be built in two steps: first we’ll find the editing distance, and then use it to construct the answer.
Finding the Editing Distance
First, let
dp(i, j) = the minimum number of edits required for the problem with strings source[i:] and target[j:]. We will perform what is known as “top-down dynamic programming.” What this means is: Since dp(i, j) may depend only on the values of source[i], target[j], dp(i+1, j), dp(i, j+1), and dp(i+1, j+1), we can write a function dp(i, j) that returns the desired answer recursively in terms of these values.
Additionally, every time we calculate
dp(i, j), we will remember the result and record it in memo[i][j]. That ensures that we only perform the effort of calculating dp(i, j) once: afterwards, we simply return the cached result.
In general, when
source[i] == target[j], then dp(i, j) = dp(i+1, j+1), because we simply write source[i]. When source[i] != target[j], then we either edited source[i](subtraction) and have the problem of transforming source[i+1:]to target[j:] left over (which has answer dp(i+1, j)), or we edited target[j] (addition) and have the problem of transforming source[i:] to target[j+1:] left over (which has answer dp(i, j+1)).
Let’s look at the first part of our solution:
function diffBetweenTwoStrings(source, target):
# memo[i][j] will be our cached answer to dp(i, j)
memo = new Array(source.length, target.length)
# dp(i, j) is the minimum edits to transform
# string source[i:] into string target[j:].
function dp(i, j):
# If one of the strings is empty, we know
# the answer already.
if i == source.length OR j == target.length:
return target.length - j
# Otherwise, if we don't have a cached answer,
# then find one.
else if memo[i][j] == null:
if source[i] == target[j]:
memo[i][j] = dp(i+1, j+1)
else:
memo[i][j] = 1 + min(dp(i+1, j), dp(i, j+1))
return memo[i][j]
Constructing the Answer
Now we need to build our answer. We should iterate through the source and target, and in each step decide whether we need to delete or add another letter.
To figure this out, we need to leverage this information available in dp(i, j). When we have a decision to make between subtracting source[i] or adding target[j], we will use our knowledge of the minimum edit distances dp(i+1, j) and dp(i, j+1) to make our decision.
function diffBetweenTwoStrings(source, target):
ans = []
i = 0
j = 0
# We are always considering strings source[i:] and target[j:]
while i < source.length AND j < target.length:
if source[i] == target[j]:
# Write the string with no edits
ans.push(source[i])
i += 1
j += 1
else:
# We have to decide whether to subtract source[i],
# or add target[j].
if dp(i+1, j) <= dp(i, j+1):
ans.push('-' + source[i])
i += 1
else:
ans.push('+' + target[j])
j += 1
while j < target.length:
ans.push('+' + target[j])
j += 1
return " ".join(ans)
We could have also used a “bottom-up” dynamic program for calculating the initial edit-distance function, as follows:
function diffBetweenTwoStrings(source, target):
dp = new Array(source.length + 1, target.length + 1)
for i from 0 to source.length:
dp[i][target.length] = 0
for j from 0 to target.length:
dp[source.length][j] = target.length - j
for i from source.length - 1 to 0:
for j from target.length - 1 to 0:
if source[i] == target[j]:
dp[i][j] = dp[i+1][j+1]
else:
dp[i][j] = 1 + min(dp[i+1][j], dp[i][j+1])
Instead of caching our results, we compute them in an order that guarantees the components used in computing our answer are correct.
Here, in the main “for i from source.length - 1 to 0, for j from target.length -1 to 0” loop, we iterated i and j in an order that guaranteed that dp[i+1][j], dp[i][j+1], and dp[i+1][j+1] are correct.
The rest of the solution proceeds similarly.
Time Complexity:
O(S.length * T.length), from our construction of dp.
Space Complexity:
O(S.length * T.length), the space taken by dp.
