Dynamic Programming: Minimum number of deletions and insertions to convert one string into another

Problem Statement:

You are given 2 strings, you need to get the minimum number of insertions and deletions to convert string a to string b.

Example

Input:
str1: heap
str2: pea

Minimum insertion: 1
Minimum deletions: 2

So first insert “p” to string 1. It will become “pheap”. Then delete “h p” then the string 1 will be “pea”, that is equal to string 2.

So 1 is the minimum number of insertion and 2 is the min number of deletion.

Solution

Continuing from above statement, you can see that “ea” is the LCS of the 2 strings.

Then you need to delete 2 characters from str1 “heap” -> “ea”. Then add “p” to the resultant string to make it as str2.

So for that str1 – LCS will give min number of deletions.
str2 – LCS will give min number of additions

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <unordered_map> 
#include <list> 

using namespace std;


int lcs_bottom_up(string text1, string text2) {
    vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
    for (int i = 1; i <= text1.size(); ++i) {
        for (int j = 1; j <= text2.size(); ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[text1.size()][text2.size()];
}


void get_min_max_count (string str1, string str2)
{

  int LCS = lcs_bottom_up(str1, str2);

  cout<<"The min number of deletion "<<str1.size() - LCS<<endl;
  cout<<"The min number of insertion "<<str2.size() - LCS<<endl;
}

int main()
{   
    string str1 = "heap";
    string str2 = "pea";

    get_min_max_count(str1, str2);
  
}

Output:

The min number of deletion 2
The min number of insertion 1