Recursion

Edit Distance

You're given two strings string1 and string2. Find the minimum number of edits you need in order to turn one string into the other string. An "edit" is when you insert, delete, or change out a character from either string.

Example 1:

\notag \begin{align*} & \texttt{string1 = "abc"} \\ & \texttt{string2 = "abz"} \\[10 bp] & \texttt{=> returns 1} \\ \end{align*}

Explanation: You can change string1 into string2 by changing out the c to a z, which is 1 edit.

Example 2:

\notag \begin{align*} & \texttt{string1 = "abc"} \\ & \texttt{string2 = "abcd"} \\[10 bp] & \texttt{=> returns 1} \\ \end{align*}

Explanation: You can change string2 into string1 by inserting the character d, which is 1 edit.

First Few Test Cases:

1. Recursion

To solve this problem, you want to write numEdits using recursion. The trick to doing this is to only consider the very leftmost character in each of the strings.

The first case is when the leftmost characters are equal. In this case, you don't need to edit the first character of the strings, so you should return the edit distance of the remaining parts of the strings.

The second case is when the leftmost characters are not equal, and you need to make an edit to make them equal. You can consider all the possible edits, and take a min over them to find the minimum number of edits. Here's the recursion for this case:

Here is the official recursion, combining these two cases:

Recursing on strings is slow because strings are immutable, and it's always better to recurse on numbers instead. To do this, you can make the inputs be the number of cuts you've made from first string and the second string, which we'll call i and j. Here's the new recursion:

2. Base case

The recursion stops working when one of the strings is empty "". In this case you have to delete all of the letters from the remaining string, or add all the letters to the empty string, or some mix of the two. Either way, the edit distance is len(s).

3. Code

To code this up, we can use Tabulation. We'll store the results in a 2D array, and we can compute largest i and j first, and smallest indexes last.

Time Complexity $O(mn)$ to create the array and for the recursion's double for loop.

Space Complexity $O(mn)$ for the array.

Tabulation+

You can optimize the above solution using Tabulation+, where you throw out old values to save memory. This is because numEdits only depends on numEdits of the previous i and j, so you only need to remember the previous layer of $\tt i$ s or previous layer of $\tt j$ s. You can choose whichever is smaller to get the best space complexity. We just wanted to mention this. This would be a lot to ask in an interview.

Time Complexity $O(mn)$

Space Complexity $O(\min(m,n))$

Note: "Edit Distance" is also called Levenshtein distance.

Computing Edits: If you want to track the exact insertions/deletions needed to get the best score, you've pretty much done all the work. Just keep a pointer to $i$ and $j$ that were optimal at each point as you did DP. At the end, you can traverse these pointers to figure out all the optimal edits. This is true for any DP problem.

For Edit Distance, a further optimization for computing the exact insertions/deletions is called the Myers Diff algorithm, and it's used in tools like git and VS Code.

Mark as Completed:

Submits:

editDistance

Test your code to get an output here!

editDistance(

)

Test your code to get an output here!