### 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:

- Create DP table of size
`(s1.len +1 ) X (s2.len +1 )`

- Populate table for base cases i.e. when s1 or s2 is empty
- Iterate
`i from 1 to s1.len`

- Iterate
`j from 1 to s2.len`

- 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]}`

- If

- Iterate

Latest Source Code:

Github: MinimumEditDistance.java

**Output:**

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