Given two strings s and t, return TRUE if s is a subsequence of t

Method 1

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); 
} 

Method 2

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;

Method 3

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;
    }
Comments (0)