Edit Distance DP Problem

Edit distance problems is: if we are given two string word1 and word2 what is the minimum number of operation needed to transform a into b. The operations are: substitution, insertion and deletion. You can find this problem in interviewbit and leetcode.

In order to solve this problem, we have to be familiar with sub-string operation. Substations are contiguous sequence of characters within a string( from Wikipedia).Let’s say we have a string “horse” which goes from index 0 to 4. So, the sub-strings are: index ( 0, 0) -> ‘h’, (0,1) -> ‘ho’, (0 , 2)-> hor, (0, 3)-> ‘hors’, (0, 4) -> ‘horse’.

Now, lets see the scenarios we will face while transforming one string to another. There are four scenarios.

1. characters are same, so we do nothing
2. Characters are different, so we do substitution
3. Characters are different, so we do insertion
4. Characters are different, so we do deletion

1.Characters are same, so we do nothing

To transform the sub-string a[0, 3]( “abcd”) to b[0,3](“ xyzd”) we will start comparing the string in reverse order. As the last character of both the strings are same, we will do nothing. That means number of operation that we will need to do for substring a[0,3] and b[0,3] will be equal to the number of operation we need to do for substrings a[0,2] and b[0,2]. Because the character ‘d’ is the same, so we won’t have to do any operations to transform them.