Check if a string is a subsequence of another string ( using Stacks ) | C ++ Program for the above approach ; Function to check if target is a subsequence of string S ; Declare a stack ; Push the characters of target into the stack ; Traverse the string S in reverse ; If the stack is empty ; if S [ i ] is same as the top of the stack ; Pop the top of stack ; Stack s is empty ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void checkforSubsequence ( string S , string target ) { stack < char > s ; for ( int i = 0 ; i < target . size ( ) ; i ++ ) { s . push ( target [ i ] ) ; } for ( int i = ( int ) S . size ( ) - 1 ; i >= 0 ; i -- ) { if ( s . empty ( ) ) { cout << " Yes " << endl ; return ; } if ( S [ i ] == s . top ( ) ) { s . pop ( ) ; } } if ( s . empty ( ) ) cout << " Yes " << endl ; else cout << " No " << endl ; } int main ( ) { string S = " KOTTAYAM " ; string target = " KOTA " ; checkforSubsequence ( S , target ) ; return 0 ; }