×

Algorithms Tutorial

Searching Algorithms

Dynamic Programming

Graph Algorithms

Backtracking Algorithms

Recursion

Operating System Algorithms

Miscellaneous Topics

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 jth cell of ith row represents the minimum number of changes needed to change s1(ith index to end) and s2(jth index to end). Now if an ith character of s1 is equal to a jth 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 ith character of the s1 or jth character of s2, replace the ith character of s1 with the jth 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 jth cell of ith row represents the minimum number of ways to change the string s1 (from ith index to last) and string s2 (jth 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 Nth row and Mth column (right to left and down to up).
  5. Find the answer of each row by using dp relations.
  6. If ith character of s1 is same as a jth 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 jth cell of an ith 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   

Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.