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 Implementationof the above idea.
C/C++
// Recursive C++ program to check if a string is subsequence of another string #include<iostream> #include<cstring> using namespace std; // Returns true if str1[] is a subsequence of str2[]. m is // length of str1 and n is length of str2 bool isSubSequence( char str1[], char str2[], int m, int n) { // Base Cases if (m == 0) return true ; if (n == 0) return false ; // If last characters of two strings are matching if (str1[m-1] == str2[n-1]) return isSubSequence(str1, str2, m-1, n-1); // If last characters are not matching return isSubSequence(str1, str2, m, n-1); } // Driver program to test methods of graph class int main() { char str1[] = "gksrek" ; char str2[] = "geeksforgeeks" ; int m = strlen (str1); int n = strlen (str2); isSubSequence(str1, str2, m, n)? cout << "Yes " : cout << "No" ; return 0; } |
Java
// Recursive Java program to check if a string // is subsequence of another string import java.io.*; class SubSequence { // Returns true if str1[] is a subsequence of str2[] // m is length of str1 and n is length of str2 static boolean isSubSequence(String str1, String str2, int m, int n) { // Base Cases if (m == 0 ) return true ; if (n == 0 ) return false ; // If last characters of two strings are matching if (str1.charAt(m- 1 ) == str2.charAt(n- 1 )) return isSubSequence(str1, str2, m- 1 , n- 1 ); // If last characters are not matching return isSubSequence(str1, str2, m, n- 1 ); } // Driver program public static void main (String[] args) { String str1 = "gksrek" ; String str2 = "geeksforgeeks" ; int m = str1.length(); int n = str2.length(); boolean res = isSubSequence(str1, str2, m, n); if (res) System.out.println( "Yes" ); else System.out.println( "No" ); } } // Contributed by Pramod Kumar |
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" # This code is contributed by BHAVYA JAIN |
C#
// Recursive C# program to check if a string // is subsequence of another string using System; class GFG { // Returns true if str1[] is a // subsequence of str2[] m is // length of str1 and n is length // of str2 static bool isSubSequence( string str1, string str2, int m, int n) { // Base Cases if (m == 0) return true ; if (n == 0) return false ; // If last characters of two strings // are matching if (str1[m-1] == str2[n-1]) return isSubSequence(str1, str2, m-1, n-1); // If last characters are not matching return isSubSequence(str1, str2, m, n-1); } // Driver program public static void Main () { string str1 = "gksrek" ; string str2 = "geeksforgeeks" ; int m = str1.Length; int n = str2.Length; bool res = isSubSequence(str1, str2, m, n); if (res) Console.Write( "Yes" ); else Console.Write( "No" ); } } // This code is contributed by nitin mittal. |
PHP
<?php // Recursive PHP 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 function isSubSequence( $str1 , $str2 , $m , $n ) { // Base Cases if ( $m == 0) return true; if ( $n == 0) return false; // If last characters of two // strings are matching if ( $str1 [ $m - 1] == $str2 [ $n - 1]) return isSubSequence( $str1 , $str2 , $m - 1, $n - 1); // If last characters // are not matching return isSubSequence( $str1 , $str2 , $m , $n - 1); } // Driver Code $str1 = "gksrek" ; $str2 = "geeksforgeeks" ; $m = strlen ( $str1 ); $n = strlen ( $str2 ); $t = isSubSequence( $str1 , $str2 , $m , $n ) ? "Yes " : "No" ; if ( $t = true) echo "Yes" ; else echo "No" ; // This code is contributed by ajit ?> |
Output :
Yes
Following is the Iterative Implementation:
C/C++
// Iterative C++ program to check if a string is subsequence of another string #include<iostream> #include<cstring> using namespace std; // Returns true if str1[] is a subsequence of str2[]. m is // length of str1 and n is length of str2 bool isSubSequence( char str1[], char str2[], int m, int n) { int j = 0; // For index of str1 (or subsequence // Traverse str2 and str1, and compare current character // of str2 with first unmatched char of str1, if matched // then move ahead in str1 for ( int i=0; i<n&&j<m; i++) if (str1[j] == str2[i]) j++; // If all characters of str1 were found in str2 return (j==m); } // Driver program to test methods of graph class int main() { char str1[] = "gksrek" ; char str2[] = "geeksforgeeks" ; int m = strlen (str1); int n = strlen (str2); isSubSequence(str1, str2, m, n)? cout << "Yes " : cout << "No" ; return 0; } |
Java
// Iterative Java program to check if a string // is subsequence of another string import java.io.*; class GFG { // Returns true if str1[] is a subsequence // of str2[] m is length of str1 and n is // length of str2 static boolean isSubSequence(String str1, String str2, int m, int n) { int j = 0 ; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1, if matched // then move ahead in str1 for ( int i = 0 ; i < n && j < m; i++) if (str1.charAt(j) == str2.charAt(i)) j++; // If all characters of str1 were found // in str2 return (j == m); } // Driver program to test methods of // graph class public static void main (String[] args) { String str1 = "gksrek" ; String str2 = "geeksforgeeks" ; int m = str1.length(); int n = str2.length(); boolean res = isSubSequence(str1, str2, m, n); if (res) System.out.println( "Yes" ); else System.out.println( "No" ); } } // This code is contributed by Pramod Kumar |
Python
# Iterative 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, n is length of str2 def isSubSequence(str1,str2,m,n): j = 0 # Index of str1 i = 0 # Index of str2 # Traverse both str1 and str2 # Compare current character of str2 with # first unmatched character of str1 # If matched, then move ahead in str1 while j<m and i<n: if str1[j] = = str2[i]: j = j + 1 i = i + 1 # If all characters of str1 matched, then j is equal to m return j = = m # Driver Program str1 = "gksrek" str2 = "geeksforgeeks" m = len (str1) n = len (str2) print "Yes" if isSubSequence(str1,str2,m,n) else "No" # Contributed by Harshit Agrawal |
C#
// Iterative C# program to check if a string // is subsequence of another string using System; class GFG { // Returns true if str1[] is a subsequence // of str2[] m is length of str1 and n is // length of str2 static bool isSubSequence( string str1, string str2, int m, int n) { int j = 0; // Traverse str2 and str1, and compare // current character of str2 with first // unmatched char of str1, if matched // then move ahead in str1 for ( int i = 0; i < n && j < m; i++) if (str1[j] == str2[i]) j++; // If all characters of str1 were found // in str2 return (j == m); } // Driver program to test methods of // graph class public static void Main () { String str1 = "gksrek" ; String str2 = "geeksforgeeks" ; int m = str1.Length; int n = str2.Length; bool res = isSubSequence(str1, str2, m, n); if (res) Console.WriteLine( "Yes" ); else Console.WriteLine( "No" ); } } // This code is contributed by anuj_67. |
PHP
<?php // Iterative PHP 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 function isSubSequence( $str1 , $str2 , $m , $n ) { // For index of str1 $j = 0; // Traverse str2 and str1, // and compare current // character of str2 with // first unmatched char of // str1, if matched then // move ahead in str1 for ( $i = 0; $i < $n and $j < $m ; $i ++) if ( $str1 [ $j ] == $str2 [ $i ]) $j ++; // If all characters of // str1 were found in str2 return ( $j == $m ); } // Driver Code $str1 = "gksrek" ; $str2 = "geeksforgeeks" ; $m = strlen ( $str1 ); $n = strlen ( $str2 ); if (isSubSequence( $str1 , $str2 , $m , $n )) echo "Yes " ; else echo "No" ; // This code is contributed by anuj_67. ?> |
Output:
Yes
Asked in:
Time Complexity of both implementations above is O(n) where n is the length of str2.
leave a comment
0 Comments