Posts

Showing posts from June, 2017

Minimum Number of Insertion, Deletion and Updation to convert one string to another - Dynamic Programming

In today's post, we will be seeing on how to convert a given string to another with the minimum number of insertions, deletions or updations. I'm considering the fact that converting string A to string B will take the same number of operations as converting string B to string A, only the nature of the operation is different (insertion instead of deletion).

The Algorithm

Let us consider converting string A to string B and let length(string A) > length(string B). So converting string A to string B would take a series of deletion operations followed by updations. The only thing that we need to consider while deleting is that we need to maximize the number of common characters at the same indices after deleting. Let me take an example to explain.

Let string A = "bacad" and string B = "bece". The difference between the length of A and B is 1 and so we need to delete one character. There are 5 characters in string A and so there are 5 different deletions possi…