{"id":26965,"date":"2018-01-05T21:06:15","date_gmt":"2018-01-05T15:36:15","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26965"},"modified":"2018-01-05T21:06:15","modified_gmt":"2018-01-05T15:36:15","slug":"python-programming-given-two-strings-find-first-string-sub-sequence-second","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/python-programming-given-two-strings-find-first-string-sub-sequence-second\/","title":{"rendered":"Python Programming – Given two strings, find if first string is a subsequence of second"},"content":{"rendered":"

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.<\/p>\n

Examples:<\/strong><\/p>\n

Input: str1 = “AXY”, str2 = “ADXCPY”
\nOutput: True (str1 is a subsequence of str2)<\/p>\n

Input: str1 = “AXY”, str2 = “YADXCP”
\nOutput: False (str1 is not a subsequence of str2)<\/p>\n

Input: str1 = “gksrek”, str2 = “geeksforgeeks”
\nOutput: True (str1 is a subsequence of str2)<\/p>\n

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.<\/p>\n

Following is Recursive Implementation<\/strong><\/p>\n

Python<\/span> <\/div> 
# 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 str2def 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 functionstring1 = "gksrek"string2 = "geeksforgeeks"m = len(string1)n = len(string2)if isSubSequence(string1, string2, m, n):    print "Yes"else:    print "No"<\/code><\/pre> <\/div>\n
Output:<\/p>\n
Yes<\/pre>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
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<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,1],"tags":[75821,70483,71496,74979,80458,80454,80455,80463,77975,80465,80460,80461,73031,80453,77436,77429,73588,80464,80467,73395,73555,80456,73188,80459,80466,80457],"class_list":["post-26965","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-coding","tag-dynamic-programing","tag-dynamic-programming","tag-dynamic-programming-algorithm","tag-fibonacci-python","tag-format-python","tag-how-to-print-in-python","tag-integer-python","tag-lcs-algorithm","tag-print-python","tag-python-format","tag-python-format-print","tag-python-function","tag-python-list","tag-python-multithreading","tag-python-slice-string","tag-python-string-functions","tag-python-string-substring","tag-python-type","tag-raw-string-python","tag-string-in-c","tag-string-in-python","tag-string-length-in-c","tag-string-match","tag-string-parse","tag-string-pool-in-java","tag-variables-in-python"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26965","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26965"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26965\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26965"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26965"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26965"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}