# Python Programming – Given two strings, find if first string is a subsequence of second

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

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

Python
``````# Recursive Python program to check if a string is subsequence
# of another string

# Returns true if str1[] is a subsequence of str2[]. m is
# length of str1 and n is length of str2
def isSubSequence(string1, string2, m, n):
# Base Cases
if m == 0:    return True
if n == 0:    return False

# If last characters of two strings are matching
if string1[m-1] == string2[n-1]:
return isSubSequence(string1, string2, m-1, n-1)

# If last characters are not matching
return isSubSequence(string1, string2, m, n-1)

# Driver program to test the above function
string1 = "gksrek"
string2 = "geeksforgeeks"
m = len(string1)
n = len(string2)
if isSubSequence(string1, string2, m, n):
print "Yes"
else:
print "No"``````

Output:

`Yes` 