determining a string is subsequence of another
#include <iostream>
#include <string>
bool isSubsequence(const std::string& s, const std::string& t) {
int sLen = s.length();
int tLen = t.length();
int i = 0; // Pointer for string s
int j = 0; // Pointer for string t
// Traverse both strings
while (i < sLen && j < tLen) {
// If characters match, move pointer for s
if (s[i] == t[j]) {
i++;
}
// Move pointer for t in any case
j++;
}
// If all characters in s are found in t in the same order
return (i == sLen);
}
int main() {
std::string s = "abc";
std::string t = "ahbgdc";
if (isSubsequence(s, t)) {
std::cout << s << " is a subsequence of " << t << std::endl;
} else {
std::cout << s << " is not a subsequence of " << t << std::endl;
}
return 0;
}
Explanation:
- isSubsequence
function takes in two strings s
and t
.
- sLen
and tLen
store the lengths of strings s
and t
, respectively.
- Pointers i
and j
are initialized to 0 to traverse through s
and t
.
- While both pointers i
and j
are within bounds:
- If characters at s[i]
and t[j]
match, move the pointer i
for string s
.
- Move pointer j
for string t
in any case.
- Return true
if all characters in s
are found in t
in the same order, checked by comparing the final value of i
with the length of s
.
- In the main
function, it demonstrates the usage by checking if string s
is a subsequence of string t
, and prints the result accordingly.