Given two strings str1 of size m and str2 of size n, check if the 2nd string can be obtained from the 1st string in the same order as in the 2nd string. If the 2nd string is obtained then print “YES”, else print “NO”.
Examples :
Input : str1 = "kakapleplek" str2 = "apple" Output : YES Explanation : str2[0] matched with str1[1] str2[1] matched with str1[4] str2[2] matched with str1[7] str2[3] matched with str1[8] str2[4] matched with str1[9] All matched in order, output "YES" Input : str1 = "kakaplep" str2 = "apple" Output : NO Input : str1 = "stiurf" str2 = "fruits" Output : NO Input : str1 = "cake" str2 = "" Output : YES
Approach :
We will iterate through string str1 from left to right to search for each character of the string str2 in order. If all characters found in the string str1 of the string str2 then we will stop the iteration and print “YES”, else we will print “NO”.
Implementation :
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if both strings are matched
void check(string str1, string str2)
{
int m = str1.size();
int n = str2.size();
// Checking if str2 is empty
if (n == 0) {
cout << "YES";
return;
}
// Initializing index for track of string str2
int index = 0;
// Iterating through string str1
for (int i = 0; i < m; i++) {
// Checking characters of each string matched
if (str1[i] == str2[index])
index++;
// Checking if all characters of string str2 are
// matched
if (index == n) {
cout << "YES";
return;
}
}
// Loop ended means both strings aren't matched
cout << "NO";
}
// Driver Code
int main()
{
string str1 = "kakapleplek";
string str2 = "apple";
check(str1, str2);
return 0;
}
Output :
YES
Time complexity : O(m + n)
Auxiliary space : O(1)