Given 2 strings like bangalore and blr, return whether one appears as a subsequence of the other. The above case returns true whereas bangalore and brl returns false.
Greedy strategy should work for this problem.
Here is a sample code in C++:
#include <iostream>
#include <string>
using namespace std;
int main() {
string txt = "quick brown fox jumps over the lazy dog";
string s = "brownfoxzdog";
int pos = -1;
bool ok = true;
for (int i = 0 ; ok && i != s.size() ; i++) {
ok = (pos = txt.find(s[i], pos+1)) != string::npos;
}
cerr << (ok ? "Found" : "Not found") << endl;
return 0;
}
// Solution 1
public static boolean isSubSequence(String str1, String str2) {
int i = 0;
int j = 0;
while (i < str1.length() && j < str2.length()) {
if (str1.charAt(i) == str2.charAt(j)) {
i++;
j++;
} else {
i++;
}
}
return j == str2.length();
}
// Solution 2 using String indexOf method
public static boolean isSubSequenceUsingIndexOf(String mainStr, String subStr) {
int i = 0;
int index = 0;
while(i<subStr.length()) {
char c = subStr.charAt(i);
if((index = mainStr.indexOf(c, index)) == -1) {
return false;
}
i++;
}
return true;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With