Dynamic Programming: Get the count of delete operations on 2 strings.

Problem Statement:

You are given 2 strings, you need to return the minimum number of delete operations needed to make str1 and str 2 same.

Example

Input: str1 = “sea”, str2 = “eat”
Output: 2

Delete one char from “sea” to “ea”,

then delete one char from “eat” to “ea”

Solution

From the above explanation, it is clear that we need to find the longest common subsequence of 2 strings.

Then subtract the length from both of the strings, to get the min delete operation.

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_delete_count (string str1, string str2)
{

  int LCS = lcs_bottom_up(str1, str2);

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

int main()
{   
    string str1 = "sea";
    string str2 = "eat";

    get_min_delete_count(str1, str2);
  
}

Output:

The min number of deletion 2