Edit Distance Problem

This is a C++ Program that Solves Edit Distance Problem using Dynamic Programming technique.

Problem Description

There are two strings src and dest. The goal of the problem is to convert src to dest by applying minimum edit operations on string str1. The edit operations are following –

1) insert a character
2) delete a character
3) replace a character

Problem Solution

This problem can be solved optimally using bottom up DP. We will first calculate minimum operations required to transform a prefix of the string src to a prefix of string dest. Then we will use this information to calculate minimum no. of operations required to transform a bigger prefix of src to a bigger prefix of dest.

The time complexity of this solution will be O(len1*len2).

Expected Input and Output

Case-1:

str1="vish"
str2="vishal"
 
Minimum number of edit operations=2
inserting 2 chracters 'a' and 'l'

Case-2:

str1="vshkl"
str2="vishal"
 
Minimum number of edit operations=2
inserting 'i' and replacing 'k' with 'a'

Case-3:

Subscribe Now: Dynamic Programming Newsletter | Important Subjects Newsletters

str1="apiskal"
str2="vishal"
 
Minimum number of edit operations=3
deleting 'a', replacing 'p' with 'v' and replacing 'k' with 'h'

Program/Source Code for Brute Force Solution

Here is source code of the C++ Program to Solve Edit Distance Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<string>
```
```
 
```
```
using namespace std;
```
```
 
```

//we will be processing the src and dest string from the rear end.

//If the current character matches in both string, we proceed for next character.

//else we will apply all the 3 operations one by one, and select the one which takes

//minimum number of overall edit operations to convert src to dest

int minEditDistanceBrute(string src, string dest, int len1, int len2)

```
{
```

    //if we have already attained the dest string, we can simply remove the left out characters in src string

```
    if(len2==0)
```
```
    {
```
```
        return len1;
```
```
    }
```
```
 
```

    //if the entire src string is process, we can simply insert all the remaining characters of dest string

```
    if(len1==0)
```
```
    {
```
```
        return len2;
```
```
    }
```
```
 
```

    //if current character of the src and dest is same, no operation is required to be done

```
    if(src[len1-1]==dest[len2-1])
```
```
    {
```

        return minEditDistanceBrute(src, dest, len1-1, len2-1);

```
    }
```
```
 
```
```
 
```

    //if current character is different for src and dest string

```
    else
```
```
    {
```

        //if the required character of dest string is inserted in src string

        int x=1+minEditDistanceBrute(src,dest,len1,len2-1);

```
 
```

        //if the current character of src is removed

        int y=1+minEditDistanceBrute(src,dest,len1-1,len2);

```
 
```

        //if the current character of the src string is replaced with the current character of the dest string

        int z=1+minEditDistanceBrute(src,dest,len1-1,len2-1);

```
 
```
```
 
```

        //now, choose the operation which require minimum number of overall operations out of these

```
        return min(x,min(y,z));
```
```
 
```
```
    }
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    string src,dest;
```
```
 
```
```
    cout<<"Enter source string   ";
```
```
    getline(cin, src);
```
```
 
```

    cout<<"Enter destination string   ";

```
    getline(cin, dest);
```
```
 
```

    int len1=src.length();  //length of src string

    int len2=dest.length(); //length of dest string

```
 
```

    cout<<"Minimum number of edit operations required for transforming \nsource string to destination string is "<<minEditDistanceBrute(src,dest,len1,len2);

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program/Source Code for DP solution

Here is source code of the C++ Program to Solve Edit Distance Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

```
#include<iostream>
```
```
#include<string>
```
```
 
```
```
using namespace std;
```
```
 
```

int minEditDistance(string src, string dest, int len1, int len2)

```
{
```
```
    int i, j;
```
```
 
```

    //create a matrix of order (len1+1)*(len2+1) to memoize values

```
    int edit[len1+1][len2+1];
```
```
 
```

    //edit[i][j]=minimum number of edit operations required to transform src[0....(i-1)] to dest[0...(j-1)]

```
 
```
```
    //initializing
```
```
    for(i=0;i<=len1;i++)
```

        edit[i][0]=i;    //min operations required to transform src[0...i-1] to empty dest string

```
 
```
```
    for(j=0;j<=len2;j++)
```

        edit[0][j]=j;   //min operations required to transform empty src to dest[0...j-1]

```
 
```

    //now, start filling the matrix row wise

```
    for(i=1;i<=len1;i++)
```
```
    {
```
```
        for(j=1;j<=len2;j++)
```
```
        {
```

            //if current character of both strings match

```
            if(src[i-1]==dest[j-1])
```
```
            {
```

                edit[i][j]=edit[i-1][j-1];

```
            }
```
```
 
```
```
            //mismatch
```
```
            else
```
```
            {
```

                //try applying all operations and choose the one which costs minimum

                int x=1+edit[i-1][j];    //delete

                int y=1+edit[i][j-1];    //insert

                int z=1+edit[i-1][j-1];  //replace

```
 
```

                edit[i][j]=min(x,min(y,z));

```
 
```
```
            }
```
```
        }
```
```
    }
```
```
 
```
```
    //now, return the final value 
```
```
    return edit[len1][len2];
```
```
 
```
```
}
```
```
 
```
```
 
```
```
int main()
```
```
{
```
```
    string src,dest;
```
```
 
```
```
    cout<<"Enter source string   ";
```
```
    getline(cin, src);
```
```
 
```

    cout<<"Enter destination string   ";

```
    getline(cin, dest);
```
```
 
```

    int len1=src.length();  //length of src string

    int len2=dest.length(); //length of dest string

```
 
```

    cout<<"Minimum number of edit operations required for transforming \nsource string to destination string is "<<minEditDistance(src,dest,len1,len2);

```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the source and destination strings. We pass these values to the function minEditDistance as parameters. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ edit_distance_DP.cpp
$ ./a.out
Enter source string   vish
Enter destination string   vishal
Minimum number of edit operations required for transforming 
source string to destination string is 3

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.

If you find any mistake above, kindly email to [email protected]

« Prev - Dynamic Programming Solutions – Balanced Partition Problem

» Next - Optimal Strategy for a Game using Dynamic Programming

Related Posts:

Practice Design & Analysis of Algorithms MCQ
Practice Programming MCQs
Apply for Computer Science Internship
Check Programming Books
Practice Computer Science MCQs

Recommended Articles: