Home » Algorithms

Edit Distance using Dynamic Programming (DP)

Edit Distance using Dynamic Programming: Given two string s1 and s2 of length M and N respectively, we have to perform 1) Insert a character at any position, 2) Delete a character at any position, and 3) Replace a character with any character at any position.
Submitted by Ritik Aggarwal, on December 09, 2018

Problem: You are given two strings s1 and s2 of length M and N respectively. You can perform following operations on the string.

1. Insert a character at any position
2. Delete a character at any position
3. Replace a character with any character at any position

Find minimum number of ways to convert s1 into s2 using above operation only.

Constraints:

1 <= N <= 2000
1 <= M <= 2000

Example:

    Sample Input 1:
    abcde
    bcdae
    Sample Output 1:
    2

    Sample Input 2:
    dacef
    cdafe
    Sample Output 2:
    3

Explanation of the problem:

In the first sample provided above, we can delete a from s1 and insert it before e in s1. So, there are two steps.

Solution:

Before proceeding to the solution we can see that the recursive solution will be hard to implement so we will proceed to the dynamic programming approach. In this approach, the j^th cell of i^th row represents the minimum number of changes needed to change s1(i^th index to end) and s2(j^th index to end). Now if an i^th character of s1 is equal to a j^th character of s2 then we don’t have to take care of that character as it is already same so pick up the right-bottom diagonal value. If characters are not equal then we can delete the i^th character of the s1 or j^th character of s2, replace the i^th character of s1 with the j^th character of s2 or vice versa and move on to the right bottom corner. In this case, we also have to add 1 as deletion, replacement is considered as a step.

Algorithm

1. Create dp matrix in which j^th cell of i^th row represents the minimum number of ways to change the string s1 (from i^th index to last) and string s2 (j^th index to last).
2. One extra row and col are taken to build to include blank string also.
3. If s1 is blank and s2 is full we have to initialize this condition so initializing this condition doing the same thing for vice versa case.
4. Start filling dp matrix from the N^th row and M^th column (right to left and down to up).
5. Find the answer of each row by using dp relations.
6. If i^th character of s1 is same as a j^th character of s2 then store the right-bottom value.
7. Otherwise, take the minimum of downward adjacent, rightward adjacent, bottom-right adjacent value and add 1 to it and store the answer.
8. Store the answer in a j^th cell of an i^th row.

The time complexity of the above code is O (N * M).

C++ Code for Edit Distance using Dynamic Programming (DP)

#include <iostream>
#include <math.h>
using namespace std;

// function for finding edit distance
int editDistance(string s1, string s2){
    // dp matrix for storing the values
    int dp[s1.length() + 1][s2.length() + 1] = {0};
    int counter = 0;
    // loops are used to store some values necessary for dp relations as 
	// we can initialize all values to 0 in this case
    for(int row = s1.length();row>=0;row--){
        dp[row][s2.length()] = counter;
        counter++;
    }
    counter = 0;
    for(int col = s2.length();col>=0;col--){
        dp[s1.length()][col] = counter;
        counter++;
    }
    // filling the dp matrix 
    for(int row = s1.length()-1;row>=0;row--){
        for(int col = s2.length() - 1;col>=0;col--){
            // if rowth character of s1 is same as colth character of s2 
			// then store diagonally right-bottom shifted value
            if(s1[row] == s2[col]){
                dp[row][col] = dp[row+1][col+1];
            }
            // otherwise, take minimum of adjacent downward, adjacent rightward, 
			// diagonally rigth-bottom value and add 1 to it and store that value
            else{
                dp[row][col] = min(dp[row+1][col], min(dp[row][col+1], dp[row+1][col+1])) + 1;
            }
        }
    }
    return dp[0][0];
}

// driver function to test the code
int main() {
	string s1,s2;
	cin >> s1 >> s2;
	cout << s1 << "\n" << s2 << endl;
	cout<< editDistance(s1, s2);
	return 0;
}

Output

abcde
bcdae
abcde
bcdae
2