Recursion
bool isSubSeq(string str1, string str2, int m, int n)
{
// Base Cases
if (m == 0) return true;
if (n == 0) return false;
// If last characters of two strings are matching
if (str1[m-1] == str2[n-1])
return isSubSeq(str1, str2, m-1, n-1);
// If last characters are not matching
return isSubSeq(str1, str2, m, n-1);
} DP ( using LCS ) O(MN) Time & O(MN) space
bool isSubsequence(string s, string t) {
int LCS = lcs( s , t );
if(LCS==s.length( ))
return true;
else return false;2 Pointers ( Most optimal ) O(N) time & O(1) space
bool isSubsequence(string s, string t) {
int m = s.size();
int n = t.size();
int i = 0, j = 0;
while(i < m && j < n) {
if(s[i] == t[j])
i++;
j++;
}
return i == m ? true : false;
}