gistfile1.txt

// 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);
    }
};