Press "Enter" to skip to content

Minimum edit distance

Ajk 0

Today I finally decided to write down a dynamic programming question. It’s very cliche and gets asked a lot in interviews. Given two words we want to find the minimum edit distance, i.e. the minimum number of steps required to convert one to the other. The idea is to make a 2d array, where every cell A[i][j] represents the minimum edit distance between word1 with i characters and word2 with j characters.

The relation in the array is that every edit distance A[i][j] is going to be the minimum of:

  • A[i-1][j] + 1 (in case we are adding character i)
  • A[i][j-1] + 1 (in case we are adding character j)
  • A[i-1][j-1] (in case letters at i and j aren’t the same and we are changing one to the other)
  • A[i-1][j-1] (in case letters at i and j are the same so added edit distance is 0)

Below the code:

Minimum edit distance – dynamic programming.

As we can see it’s not that hard. DP is all about memorizing solutions to subproblems of our problem, so we can have them readily available. (If we were to recurse in this case, we would have had to compute some of the table cells many times).

The runtime here is O(mn) for both space and time!
Hope you guys enjoyed it… and I’ll see you guys next time.

The following two tabs change content below.
If you like one of my posts the best way to support is give it a thumbs up, comment, or share it on social media 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *