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=”python” manual=”%23%20Recursive%20Python%20program%20to%20check%20if%20a%20string%20is%20subsequence%0A%23%20of%20another%20string%0A%20%0A%23%20Returns%20true%20if%20str1%5B%5D%20is%20a%20subsequence%20of%20str2%5B%5D.%20m%20is%0A%23%20length%20of%20str1%20and%20n%20is%20length%20of%20str2%0Adef%20isSubSequence(string1%2C%20string2%2C%20m%2C%20n)%3A%0A%20%20%20%20%23%20Base%20Cases%0A%20%20%20%20if%20m%20%3D%3D%200%3A%20%20%20%20return%20True%0A%20%20%20%20if%20n%20%3D%3D%200%3A%20%20%20%20return%20False%0A%20%0A%20%20%20%20%23%20If%20last%20characters%20of%20two%20strings%20are%20matching%0A%20%20%20%20if%20string1%5Bm-1%5D%20%3D%3D%20string2%5Bn-1%5D%3A%0A%20%20%20%20%20%20%20%20return%20isSubSequence(string1%2C%20string2%2C%20m-1%2C%20n-1)%0A%20%0A%20%20%20%20%23%20If%20last%20characters%20are%20not%20matching%0A%20%20%20%20return%20isSubSequence(string1%2C%20string2%2C%20m%2C%20n-1)%0A%20%0A%23%20Driver%20program%20to%20test%20the%20above%20function%0Astring1%20%3D%20%22gksrek%22%0Astring2%20%3D%20%22geeksforgeeks%22%0Am%20%3D%20len(string1)%0An%20%3D%20len(string2)%0Aif%20isSubSequence(string1%2C%20string2%2C%20m%2C%20n)%3A%0A%20%20%20%20print%20%22Yes%22%0Aelse%3A%0A%20%20%20%20print%20%22No%22″ message=”Python” highlight=”” provider=”manual”/]Output:
Yes[ad type=”banner”]