Given two strings, find if first string is a subsequence of second - GeeksforGeeks

Given two strings, find if first string is a subsequence of second - GeeksforGeeks
Given two strings str1 and str2, find if str1 is a subsequence of str2. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements (source: wiki).
O(M+N)
we traverse both strings from one side to other side (say from rightmost character to leftmost). If we find a matching character, we move ahead in both strings. Otherwise we move ahead only in str2.

bool isSubSequence(char str1[], char str2[], int m, int n)

{

   int j = 0; // For index of str1 (or subsequence

 

   // Traverse str2 and str1, and compare current character

   // of str2 with first unmatched char of str1, if matched

   // then move ahead in str1

   for (int i=0; i<n&&j<m; i++)

       if (str1[j] == str2[i])

         j++;

 

   // If all characters of str1 were found in str2

   return (j==m);

}

Recursive Version:
T(n)=T(n-1)+1=O(n)

bool isSubSequence(char str1[], char 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 isSubSequence(str1, str2, m-1, n-1);

 

    // If last characters are not matching

    return isSubSequence(str1, str2, m, n-1);

}

Read full article from Given two strings, find if first string is a subsequence of second - GeeksforGeeks