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). Expected time complexity is linear.
Examples:
Input: str1 = “AXY”, str2 = “ADXCPY”
Output: True (str1 is a subsequence of str2)
Input: str1 = “AXY”, str2 = “YADXCP”
Output: False (str1 is not a subsequence of str2)
Input: str1 = “gksrek”, str2 = “geeksforgeeks”
Output: True (str1 is a subsequence of str2)
The idea is simple, 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.
Following is Recursive Implementation
[pastacode lang=”c” manual=”%2F%2F%20Recursive%20C%2B%2B%20program%20to%20check%20if%20a%20string%20is%20subsequence%20of%20another%20string%0A%23include%3Ciostream%3E%0A%23include%3Ccstring%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Returns%20true%20if%20str1%5B%5D%20is%20a%20subsequence%20of%20str2%5B%5D.%20m%20is%0A%2F%2F%20length%20of%20str1%20and%20n%20is%20length%20of%20str2%0Abool%20isSubSequence(char%20str1%5B%5D%2C%20char%20str2%5B%5D%2C%20int%20m%2C%20int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20Cases%0A%20%20%20%20if%20(m%20%3D%3D%200)%20return%20true%3B%0A%20%20%20%20if%20(n%20%3D%3D%200)%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20of%20two%20strings%20are%20matching%0A%20%20%20%20if%20(str1%5Bm-1%5D%20%3D%3D%20str2%5Bn-1%5D)%0A%20%20%20%20%20%20%20%20return%20isSubSequence(str1%2C%20str2%2C%20m-1%2C%20n-1)%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20last%20characters%20are%20not%20matching%0A%20%20%20%20return%20isSubSequence(str1%2C%20str2%2C%20m%2C%20n-1)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20methods%20of%20graph%20class%0Aint%20main()%0A%7B%0A%20%20%20%20char%20str1%5B%5D%20%3D%20%22gksrek%22%3B%0A%20%20%20%20char%20str2%5B%5D%20%3D%20%22geeksforgeeks%22%3B%0A%20%20%20%20int%20m%20%3D%20strlen(str1)%3B%0A%20%20%20%20int%20n%20%3D%20strlen(str2)%3B%0A%20%20%20%20isSubSequence(str1%2C%20str2%2C%20m%2C%20n)%3F%20cout%20%3C%3C%20%22Yes%20%22%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20%22No%22%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C Program” highlight=”” provider=”manual”/]Output:
Yes[ad type=”banner”]