List the Differences Between Two Strings

Solution: Dynamic Programming + Construction

Our solution will be built in two steps: first, we'll find the edit 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 memoized 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 memoized 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 memoized 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 memoizing 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(MN), where M is the length of the source string and N is the length of the target string, from our construction of memo.

Space Complexity: O(MN), where M is the length of the source string and N is the length of the target string, the space taken by memo.