Home > Applied Algorithms, Recursion, String > Edit Distance between two strings (using Recursion)

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 Brute-Force 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.length-m)

If ( String1.length == m) return (String2.length-n)

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! 🙂

Advertisements
  1. No comments yet.
  1. November 1, 2011 at 7:28 pm

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: