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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/* * Given two words find the minimum edit distance between them * defined asnumber of steps required to convert one to the other. * * "One step" is defined as: Adding, removing or replacing a character. */ package iqLib.arrayLib; public class MinimumEditDistance { public static int findMinimumEditDistance(String startWord, String endWord) { int startLength = startWord.length() + 1; int endLength = endWord.length() + 1; int[][] DP = new int[startLength][endLength]; //Initialize the starting rows. for (int i = 0; i < startLength; ++i) { DP[i][0] = i; } for (int j = 0; j < endLength; ++j) { DP[0][j] = j; } for (int i = 1; i < startLength; ++i) { for (int j = 1; j < endLength; ++j) { int changed = 1; if (startWord.charAt(i) == endWord.charAt(j)) { changed = 0; } DP[i][j] = Math.min(Math.min((DP[i-1][j]+1), (DP[i][j-1]+1)), DP[i-1][j-1]+changed); } } return DP[startLength-1][endLength-1]; } } |
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.
Latest posts by Ajk (see all)
- Find Median from Numbers Array - January 1, 2018
- Find Whether a Number Can Be the Sum of Two Squares - August 12, 2017
- How to Find Two Primes Whose Sum is Equal to a Number N - April 22, 2017