Dynamic Programming: Check if one string is a subsequence of another

Problem Statement:

Youa are given 2 strings, a, b.
You need to check if string “a” is a subsequence of string “b”

Example

Input:
str1 = “abc”
str2 = “ahbgdc”

Output: true

“abc” is a subsequence of str2.

Solution

The solution is straight forward.

You need to find if there is any subsequence of str1 in str2.

If there is then return true.

So this raises a question, when to stop ?

We can stop the LCS when the LCS length is equal to the length of str1.

Solution in C++

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

using namespace std;


bool is_subsequence_recursive(string str1, string str2, int m, int n)
{
     
    // Base Cases
    if (m == 0)
        return true;
    if (n == 0)
        return false;
 
    // if the last char of both the strings are matching
    if (str1[m - 1] == str2[n - 1])
        return is_subsequence_recursive(str1, str2, m - 1, n - 1);
 
    // if they are not matching, just decrement the second string,
    // as we want the first string in second string
    return is_subsequence_recursive(str1, str2, m, n - 1);
}


int bottom_up_util(string s, string t, int m,int n)
{
    int dp[m+1][n+1],i=0,j=0;
    for(i=0;i<=m;i++)
    for(j=0;j<=n;j++)
    {    
        if(i==0 || j==0)
            dp[i][j]=0;
    }
    for(i=1;i<=m;i++)
    for(j=1;j<=n;j++)  
    {    
        if(s[i-1]==t[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[m][n];
}
bool is_subsequence_bottom_up(string s, string t) 
{
    int m = s.length();
    int n = t.length();
    int len = bottom_up_util(s,t,m,n);

    if(len == m)
        return true;
    else
        return false;
}

int main()
{   
    string str1 = "abc";
    string str2 = "ahbgdc";

    if(is_subsequence_recursive(str1, str2, str1.size(), str2.size()))
    {
        cout<<"Substring is present using recursive" <<endl;
    } else {
        cout<<"Substring is not present using recursive" <<endl;
    }

    if(is_subsequence_bottom_up(str1, str2))
    {
        cout<<"Substring is present using bottom up" <<endl;
    } else {
        cout<<"Substring is not present using bottom up" <<endl;
    }
  
  
}

Output:

Substring is present using recursive
Substring is present using bottom up