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

Case 1: Delete 'b'
A = "acad" B = "bece"       Number of common characters with same indices = 0

Case 2: Delete 'a'
A = "bcad" B = "bece"       Number of common characters with same indices = 1

Case 3: Delete 'c'
A = "baad" B = "bece"       Number of common characters with same indices = 1

Case 4: Delete 'a'
A = "bacd" B = "bece"       Number of common characters  with same indices = 2

Case 5: Delete 'd'
A = "baca" B = "bece"       Number of common characters with same indices = 2

We need to maximize the number of common characters and so we can either choose Case 4 or Case 5. And now we have strings of common length. We can simply run a loop through the string and increment a counter when the ith index of strings don't match.

We use dynamic programming here. Dynamic programming simply said, is a carefully done brute force to reduce the time complexity. Here we store the result at the end and we use the result when we need it to reduce the number of recursive calls thereby reducing the time complexity.

Code 


Output

Minimum number of operations : 3

Comments

Popular posts from this blog

Finding the Longest Palindrome in a String

Finding a Single Number amongst Repeated Numbers [Repeated Twice]

Finding the Longest Path From One Point To Another - Dynamic Programming