Question: Find the minimum number of operations required to convert a string X of length n to another string Y of length m.

Operations allowed:

  1. Insertion
  2. Deletion
  3. Substitution

We can solve this question by solving it’s sub-problem i.e., find the minimum number of operations required to convert a string X[0,…,i] to Y[0,…j].

Base conditions:

  1. To convert a string of length n to the given string of length 0, we require n deletion operations.
  2. To convert a string of length 0 to the given string of length n, we require n insertion operations.

At every position we may come across any of these two situations:

  1. If the last character of both strings is same. In this case we don’t need to do any operation, we can simply say that the answer for this problem will be same as for the sub-problem editDistance(X[0,…,i-1] , Y[0,….,j-1]).
  2. If the last character is not same, we have to choose one of these operations:
    1. Insertion: In this case, we will insert Y[j] character at ith position and add 1 to the answer of editDistance(X[0,….i], Y[0,….,j-1]). By doing this we ensure that now the last character of both strings is same.
    2. Deletion: In this case, we will delete the ith character of X and add 1 to the answer of editDistance(X[0,….,i-1] , Y[0,…,j]). By doing this we are leaving the last character of X string i.e., deletion is performed.
    3. Substitution: In this case we will substitute X[i] by Y[j] and add 1 to the answer of editDistance(X[0,…,i-1] , Y[0,…,j-1]). This becomes the same case as having equal last character in both strings.

As we require minimum number of operations hence, we will take minimum of the three possible operations.

Implemented code in C++

#include<bits/stdc++.h>
using namespace std;
int min(int a,int b,int c){
	return min(a,min(b,c));
}
int editDistance(string X,string Y){
	int n=X.length();
	int m=Y.length();
	int ed[n+1][m+1];

	// to convert a string into null string we need to perform 
	// deletion operation n number of times where n is length of the string
	for(int i=0;i<=n;i++){
		ed[i][0]=i;
	}

	// to convert a null string into the given string we need to perform 
	// insertion operation n number of times where n is length of the string
	for(int i=0;i<=m;i++){
		ed[0][i]=i;
	}

	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(X[i-1]==Y[j-1]){
				// no operation required
				ed[i][j] = ed[i-1][j-1];
			}
			else{
				// one of the three operation required
				ed[i][j] = 1+ min( ed[i-1][j],   //deletion
                                   ed[i][j-1],   //insertion
                                   ed[i-1][j-1] //substitution
					             );
			}
		}
	}
	return ed[n][m];
}

int main()
{
	string X="abcd";
	string Y="acdef";
	int result = editDistance(X,Y);
	cout<<result<<"\n";
	return 0;
}
Output:

3

That’s all I have and thanks a lot for reading 😉 . Please let me know if any corrections/suggestions. Please do share and comments if you like the post. Thanks in advance…

Thanks Shiva Gupta for helping us to grow day by day. Shiva is an expert in Data Structure and loves to solve competitive problems.


0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert