# Levenshtein Edit Distance

Leetcode

Question. Given 2 strings A[1...n] and B[1...m], what is minimum number of edits to A required to make 2 strings identical? An edit could be 1 of the following:

• Insert a character
• Delete a character
• Replace a character

For example, when A = "FOOD", B = "MONEY", the edit distance is 4.

FOOD -> MOOD -> MOND -> MONED -> MONEY

when A = "HORSE", B = "ROS", the edit distance is 3.

HORSE -> RORSE -> ROSE -> ROS

From the example we can see that there are 3 operations at any given index i:

1. Insert(i) Cost = 1
2. Delete(i) Cost = 1
3. Replace(i, newChar) Cost = 1 if A[i] != B[i], else Cost = 0

Since we eventually need to convert this to DP, it’s easier to use string indices to keep track of which subproblem we are solving. Let’s use i for string A[1...n] and j for string B[1...n].

\text{EditDist}(i, j)

Our final result is:

\text{EditDist}(n, m)

If any of the string is empty, then the cost would be the length of that non-empty string. This will happen when we call:

{\text{EditDist}}(\red0, j)\\
\text{ or }\\
\text{EditDist}(i, \red0)

If both strings are not empty, we will try to insert, delete, or replace. These are the 3 possible choices. To make a choice:

1. Let’s consider what it really means to “insert”.

   @EX A=\texttt{"FOOD"}, B=\texttt{"MONEY"}

    \begin{matrix}
    &&&&&\Downarrow\\
    A:&\tt{F} & \tt{O}&\tt{O}&\tt{D}&\texttt{\red?}\\
    B:&\tt{M} & \tt{O}&\tt{N}&\tt{E} &\tt{\red Y} 
    \end{matrix}

   If we insert a \tt Y at the questions mark, we have an aligned column. Then we can move to the "next" by considering the column to the left.

   Maybe we can do this by i -= 1, j -= 1, now we are here:

    \begin{matrix}
    &&&&\Downarrow\\
    A:&\tt{F} & \tt{O}&\tt{O}&\tt{\red D}&\tt{\green Y}\\
    B:&\tt{M} & \tt{O}&\tt{N}&\tt{\red E} &\tt{\green Y} 
    \end{matrix}

   But notice that the question mark technically doesn’t exist because A is shorter.

    \begin{matrix}
    &&&&\overset{i}{\Downarrow}\\
    A:&\tt{F} & \tt{O}&\tt{O}&\tt{\red D}&\\
    B:&\tt{M} & \tt{O}&\tt{N}&\tt{E} &\tt{\red Y} \\
    &&&&&\underset{j}{\Uparrow}\\
    \end{matrix}

   So i is already at the position after insertion. All we need to do is move j to j-1.

    \begin{matrix}
    &&&&\overset{i}{\Downarrow}\\
    A:&\tt{F} & \tt{O}&\tt{O}&\tt{\red D}&\tt{\green Y}\\
    B:&\tt{M} & \tt{O}&\tt{N}&\tt{\red E} &\tt{\green Y} \\
    &&&&\underset{j}{\Uparrow}\\
    \end{matrix}

   Therefore the recursive call for insert is:

    \text{EditDist}(i, j-1) + 1

   +1 for the cost of insertion

2. Delete

   Delete is more straightforward. We simply don’t consider the i–th character in A.

   We can do this by moving i to i - 1.

   Therefore the recursive call for delete is:

    \text{EditDist}(i-1, j) + 1

   +1 for the cost of deletion

3. Replace

   To replace a character, we move both i and j.

   @EX A=\texttt{"FOOD"}, B=\texttt{"MONEY"}

    \begin{array}{c:}
    \text{\blue {Index}}&\blue1 & \blue2 & \blue 3 & \blue4  & \blue 5 \\
    &&&&\Downarrow\\
    A:&\tt{F} & \tt{O}&\tt{O}&\tt{\red D}&\tt{Y}\\
    B:&\tt{M} & \tt{O}&\tt{N}&\tt{\red E} &\tt{Y} 
    \end{array}\hspace{1em}\xrightarrow{\text{replace(cost 1) at index 4}}\hspace{1em}\begin{matrix}
    \blue1 & \blue2 & \blue 3 & \blue4  & \blue 5 \\
    &&\Downarrow\\
    \tt{F} & \tt{O}&\tt{\red O}&\tt{\green E}&\tt{Y}\\
    \tt{M} & \tt{O}&\tt{\red N}&\tt{\green E} &\tt{Y} 
    \end{matrix}

    \begin{array}{c:}
    \text{\blue {Index}}&\blue1 & \blue2 & \blue 3 & \blue4  & \blue 5 \\
    &&\Downarrow\\
    A:&\tt{F} & \tt{\purple O}&\tt{N}&\tt{E}&\tt{Y}\\
    B:&\tt{M} & \tt{\purple O}&\tt{N}&\tt{E} &\tt{Y} 
    \end{array}\hspace{1em}\xrightarrow{\text{replace(free) at index 2}}\hspace{1em}\begin{matrix}
    \blue1 & \blue2 & \blue 3 & \blue4  & \blue 5 \\\Downarrow\\
    \tt{\red F} & \tt{\green O}&\tt{ N}&\tt{E}&\tt{Y}\\
    \tt{\red M} & \tt{\green O}&\tt{N}&\tt{E} &\tt{Y} 
    \end{matrix}

   To find the cost, we check if the characters A[i] and B[j] are the same.

   1. If A[i] = B[j] then the replacement is free
   2. If A[i] \ne B[j] then the cost is 1

   Therefore the recursive call for replace is:

    \text{EditDist}(i-1, j-1) + \begin{cases}1 & \text{if }A[i]\ne B[j]\\
    0 & \text{if }A[i]= B[j]
    \end{cases}

Since we want the shortest distance, this falls under the best solution case and we will need a min(…) call.

Now we combine 2.2.2 and 2.2.3,

{\text{EditDist}(i, j)} = \begin{cases}
i & \text{if } j = 0\\j & \text{if } i = 0\\
\min \left.\begin{cases}

\text{Insert}\\
\text{Delete}\\
\text{Replace}\\

\end{cases}\right\} & \text{Otherwise}
\end{cases}

Convert to expressions:

{\text{EditDist}(i, j)} = \begin{cases}
i & \text{if } j = 0\\j & \text{if } i = 0\\
\min \left.\begin{cases}

\text{EditDist}(i, j-1) + 1\\
\text{EditDist}(i-1, j) + 1\\
\text{EditDist}(i-1, j-1) + \begin{cases}1 & \text{if }A[i]\ne B[j]\\
0 & \text{if }A[i]= B[j]
\end{cases}\\

\end{cases}\right\} & \text{Otherwise}
\end{cases}

Implements the above recurrence. Github

The EditDistance(i, j) call requires 2 arguments, so we can use a 2D array.

We can access the result of a previous function call by EditDist[i, j]

The final result will be in EditDist[n, m]

\text{EditDist}(i, j) needs:

• \text{EditDist}(i, j - 1)
• \text{EditDist}(i-1, j)
• \text{EditDist}(i-1, j-1)

So both the loop for i and j need to go in ascending order.

We can also save the recursion results by using the library @cache decorator. See LRU Cache.

Github

This file has DP and @cache brute force.