Skip to content

Instantly share code, notes, and snippets.

@shaobos
Created October 12, 2014 18:30
Show Gist options
  • Save shaobos/af48b6eb743d7b6b5a7d to your computer and use it in GitHub Desktop.
Save shaobos/af48b6eb743d7b6b5a7d to your computer and use it in GitHub Desktop.
// https://oj.leetcode.com/problems/distinct-subsequences/
// is my solution correct by any means?
class Solution {
public:
int numDistinct(string S, string T) {
int result = 0;
int length_S = S.size();
int length_T = T.size();
is_distinct(0, 0, S, T, result, length_S, length_T);
return result;
}
void is_distinct(int index_S, int index_T, string& S, string& T, int& result, int& length_S, int& length_T) {
if (index_S == length_S) {
return;
}
if (S[index_S] == T[index_T]) {
if (index_T == length_T-1) {
result++;
return;
}
is_distinct(index_S+1, index_T+1, S, T, result, length_S, length_T);
}
// probe one element ahead, could be very inefficient
int num_left_S = length_S - index_S - 1;
int num_left_T = length_T - index_T - 1;
if (num_left_S < num_left_T) {
return;
}
is_distinct(index_S+1, index_T, S, T, result, length_S, length_T);
}
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment