Minimum Edit Distance

Given two strings s1 and s2 and ADD, DELETE, UPDATE operations that can performed on s1. Find minimum number of operations required to convert s1 into s2.

Recursive Formula:

If s1_char == s2_char then
   return s1 -1 , s2 -1
Else
   return 1 + Min { (s1, s2 -1), (s1 -1, s2), (s1-1, s2-1) }

Dynamic Programming Formula:

If s1_ith_char == s2_jth_char then
    T[i][j] = T[i-1][j-1]
 Else
    T[i][j] = Min { T[i][j-1], T[i-1][j], T[i-1][j-1]}

Dynamic Programming Algorithm:

1. Create DP table of size (s1.len +1 ) X (s2.len +1 )
2. Populate table for base cases i.e. when s1 or s2 is empty
3. Iterate i from 1 to s1.len
   1. Iterate j from 1 to s2.len
      1. If s1_ith_char == s2_jth_char then
         1. T[i][j] = T[i-1][j-1]
      2. Else
         1. T[i][j] = Min { T[i][j-1], T[i-1][j], T[i-1][j-1]}

Latest Source Code:
Github: MinimumEditDistance.java

Output:

String1 : abde
String2: agbde
Min Operation: 1
Min Operation: 1

Video

Wiki