### Edit Distance Problem

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?

1. 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.

2. This comment has been removed by the author.

3. Initial Condition: Edit distance for m = 0 , n= 0 is 0 ie (0,0) = 0
for 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).