**Source:**http://people.csail.mit.edu/bdean/6.046/dp/

**Problem:**

Given two text strings A of length n and B of length m, you want to transform A into B with a minimum number of operations of the following types: delete a character from A, insert a character into A, or change some character in A into a new character. The minimal number of such operations required to transform A into B is called the edit distance between A and B.

Given two strings A and B, what is the path from A to B with minimum edit distance?

Given two strings A and B, what is the path from A to B with minimum edit distance?

I think it will be Levenshtein distance if the distance for insertion is same for all character pairs[replacing A with B has same cost as replacing A with G] else Dynamic Time Warp Distance.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteInitial Condition: Edit distance for m = 0 , n= 0 is 0 ie (0,0) = 0

ReplyDeletefor each (i,j) where i belongs to m and j belongs to n

check = min { i.(i - 1 , j- 1) + cost of replacement of ith and jth element(here if a[i] == b[j] then the cost will be zero)

ii.(i,j-1) + cost of insertion of the jth element

iii.(i-1,j) + cost of the insertion of the ith element

}

This problem if solved recursively will take exponential time however can be done in O(m*n) by using dynamic programming with additional O(m*n) spaces.

eg: APPLE and CAPE

Considering the cost of addition, deletion or replacement is each 1.

A P P L E

C 1 2 3 4 5

A 1 2 3 4 5

P 2 1 2 3 4

E 3 3 2 3 3

Space Optimization:

The problem can be further optimized for space by using only the last array. Thus, only additional space required will be 2* min(m,n).