Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Leetcode 115: Distinct Subsequences (recursive)
#include <iostream>
#include <string>
using namespace std;
void match(const string& s, const string& t, int idxs, int idxt, int& matches) {
if (idxt == t.size()) {
matches++;
return;
}
if (idxs == s.size()) return;
for (int i=idxs; i<s.size(); ++i) {
if (s[i] == t[idxt]) match(s, t, i+1, idxt+1, matches);
}
}
int numDistinct(string s, string t) {
if (s=="" || t=="") return 0;
int matches = 0;
match(s, t, 0, 0, matches);
return matches;
}
int main() {
//string s="babgbag"; //"rabbbit";
//string t="bag"; //"rabbit";
string s="adbdadeecadeadeccaeaabdabdbcdabddddabcaaadbabaaedeeddeaeebcdeabcaaaeeaeeabcddcebddebeebedaecccbdcbcedbdaeaedcdebeecdaaedaacadbdccabddaddacdddc";
string t="bcddceeeebecbc";
cout << numDistinct(s, t) << "\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.