Edit Distance between two strings (using Recursion)
Problem Statement: Find the edit distance between two given strings. Edit distance is the minimum number of operations required to modify one string into the second one or vice versa. The operations allowed are as follows:
1. Delete a character
2. Replace a character with another one
3. Insert a character
For example,
String 1 = Hello
String 2 = Helo
The edit distance is 1 here, since we can convert 2 > 1 by inserting an ‘l’.
Recursion is a BruteForce method to solve this because it basically checks all the possibilities and finds the minimum number of operations. I am discussing this method as it is an exhaustive approach and gives you an idea of what edit distance is. So here is how the algorithms looks:
int EditDistance ( String1, String2, m, n )
{
If ( String2.length == n ) return (String1.lengthm)
If ( String1.length == m) return (String2.lengthn)
If ( String1[m] == String2[n] ) return EditDistance(String1, String2, m+1, n+1 )
If ( String1[m] != String2[n] )
return 1+min(min(EditDistance(String1, String2, m, n+1), EditDistance(String1, String2, m+1, n)), EditDistance(String1, String2, m+1,n+1))
}
That is all! Let me explain it a little. What we are doing is moving forward through the strings until the end of any one is found. If the end is found (i.e., m/n match length) we return the length of the other string minus this string’s length as those many operations will be required from that point on. If the characters at the same position are same, then there is no problem. We move ahead. If they are not the same, then we check if the next character in the other array match this one (for detecting a required deletion/insertion).
There is a better approach, using Dynamic Programming for this problem. I’ll discuss it in the next post! 🙂

November 1, 2011 at 7:28 pmEdit Distance using Dynamic Programming « All About Algorithms