{"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 &#8211; Given two strings, find if first string is a subsequence of second"},"content":{"rendered":"<p>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<p><strong>Examples:<\/strong><\/p>\n<p>Input: str1 = \u201cAXY\u201d, str2 = \u201cADXCPY\u201d<br \/>\nOutput: True (str1 is a subsequence of str2)<\/p>\n<p>Input: str1 = \u201cAXY\u201d, str2 = \u201cYADXCP\u201d<br \/>\nOutput: False (str1 is not a subsequence of str2)<\/p>\n<p>Input: str1 = \u201cgksrek\u201d, str2 = \u201cgeeksforgeeks\u201d<br \/>\nOutput: True (str1 is a subsequence of str2)<\/p>\n<p>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<p>Following is <strong>Recursive Implementation<\/strong><\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%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\u2033 message=\u201dPython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre>Yes<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>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}]}}