The normal edit distance question has the same cost throughout. Say suppose each of the 3 operations cost differently won’t the minimum change? I am not getting the solution if the cost of each operation differs. I have seen such a question somewhere, but not able to find that question now. Please help me. I have just learnt Levenshtein Distance
No , it wont change given that all cost of each operation is positive . as the operation is positive , it will always increase the cost of previous state and we just need to find the minimum over them. and at this step after we find minimum we are always sure that in the next step the sum will only increase or remain the same , so we can easily minimise this function . you can take a few examples to see that.
The edit distance will solely depend on the value of insertion,deletion and replacement. Let T[i][j] be the edit distance for string1(X) of length i and string2(Y) of length j then the dp equation is
T[i][j] = min (
T[i][j-1]+ DCOST, …// deletion - delete the jth character from string2
T[i-1][j] + ICOST, …// insertion - insert i th character into string2
T[i-1][j-1] + (X[i] != Y[j])*RCOST…// replace if X[i]!= Y[j]
)