Distinct Subsequences Solutions in C++

// Source : https://oj.leetcode.com/problems/distinct-subsequences/
// Author : Hao Chen
// Date   : 2014-07-06


#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <iostream>
#include <string>
#include <map>
#include <vector>
using namespace std;

//=====================
// Dynamic Programming
//=====================
//
//  The idea as below:
//
//     Considering m[i][j] means the distance from T[i] to S[j], and add the empty "" case, then,
//
//     A) Initialization for empty case:  m[0][j] = 1;
//
//     B) Calculation 
//
//        a) Target-len > Source-len cannot found any substring
//           i > j : m[i][j] = 0;   
//
//        b) if not equal, take the value of T[i] => S[j-1] (e.g. ["ra" => "rabb"] =["ra" => "rab"] )
//           S[j] != T[i] :  m[i][j] = m[i][j-1]
//
//        c) if equal. (e.g.  ["rab" => "rabb"] = ["rab" =>"rab"] + ["ra" => "rab"] ) 
//           S[j] == T[i] :  m[i][j] = m[i][j-1] + m[i-1][j-1]
//
//  1) Initialize a table as below   
//       ""  r  a  b  b  b  i  t
//    ""  1  1  1  1  1  1  1  1
//    r     
//    b   
//    t  
//
//  2) Calculation
//       ""  r  a  b  b  b  i  t
//    ""  1  1  1  1  1  1  1  1
//    r   0  1  1  1  1  1  1  1 
//    b   0  0  0  1  2  3  3  3
//    t   0  0  0  0  0  0  0  3
//
int numDistinct1(string S, string T) {
    vector< vector<int> > m(T.size()+1, vector<int>(S.size()+1));
    
    for (int i=0; i<m.size(); i++){
        for (int j=0; j<m[i].size(); j++){

            if (i==0){
                m[i][j] = 1;
                continue;
            }
            if ( i>j ) {
                m[i][j] = 0;
                continue;
            }
            if (S[j-1] == T[i-1]){
                m[i][j] = m[i][j-1] + m[i-1][j-1];
            } else {
                m[i][j] = m[i][j-1] ;
            }
        }
    }
    return m[T.size()][S.size()];
}


//=====================
// Dynamic Programming
//=====================
//
//  The idea here is an optimization of above idea 
//  (It might be difficult to understand if you don't understand the above idea)
//
//    For example:
//
//      S = "abbbc"  T="abb"
//      posMap = { [a]={0}, [b]={2,1} } <- the map of T's every char.
//      numOfSubSeq = {1, 0, 0, 0 }
//
//      S[0] is 'a', pos is 0,  numOfSubSeq = {1, 0+1, 0, 0};
//
//      S[1] is 'b', pos is 2,  numOfSubSeq = {1, 1, 0, 0+0};
//                   pos is 1,  numOfSubSeq = {1, 1, 0+1, 0};
//
//      S[2] is 'b', pos is 2,  numOfSubSeq = {1, 1, 1, 0+1};
//                   pos is 1,  numOfSubSeq = {1, 1, 1+1, 1};
//
//      S[3] is 'b', pos is 2,  numOfSubSeq = {1, 1, 2, 2+1};
//                   pos is 1,  numOfSubSeq = {1, 1, 1+2, 3};
//
//      S[4] is 'c', not found, numOfSubSeq = {1, 1, 3, 3};
// 
//
int numDistinct2(string S, string T) {

    map< char, vector<int> > pos_map;
    int len = T.size();
    vector<int> numOfSubSeq(len+1);
    numOfSubSeq[0] = 1;

    for (int i=len-1; i>=0; i--){
        pos_map[T[i]].push_back(i);
    }
    
    for (int i=0; i<S.size(); i++){
        char ch = S[i];
        if ( pos_map.find(ch) != pos_map.end() ) {
            for (int j=0; j<pos_map[ch].size(); j++) {
                int pos = pos_map[ch][j];
                numOfSubSeq[pos+1] += numOfSubSeq[pos];
            } 
        }
    }

    return numOfSubSeq[len];
}


//random invoker
int numDistinct(string S, string T) {
    srand(time(0));
    if (rand()%2){
        cout << "-----Dynamic Programming Method One-----" << endl;
        return numDistinct1(S,T);
    }
    cout << "-----Dynamic Programming Method Two-----" << endl;
    return numDistinct2(S,T);
}


int main(int argc, char** argv)
{
    string s = "rabbbit";
    string t = "rabbit";
    if (argc>2){
        s = argv[1];
        t = argv[2];
    }
    cout << "S=\"" << s << "\"  T=\"" << t << "\"" << endl;
    cout << "numDistinct = " << numDistinct(s, t) << endl;
    return 0;
}

#include <string>
using std::string;
#include <vector>
using std::vector;

class Solution {
public:
    int numDistinct(string S, string T) {
        int m = static_cast<int>(S.size());
        int n = static_cast<int>(T.size());
        if (m < n) return 0;
        vector<int> v(n+1, 0); v[0] = 1;
        for (int i=1; i<=m; ++i)
            for (int j=std::min(i, n)+1; j>0; --j)
                if(S[i-1] == T[j-1]) v[j] += v[j-1];
        
        return v.back();
    }
};

/// Source : https://leetcode.com/problems/distinct-subsequences/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(s * t)
/// Space Complexity: O(s * t)
class Solution {
public:
    int numDistinct(string s, string t) {

        vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
        for(int i = 0 ; i <= s.size() ; i ++)
            dp[i][0] = 1;

        for(int i = 1 ; i <= s.size() ; i ++)
            for(int j = 1 ; j <= t.size() ; j ++){
                dp[i][j] = dp[i - 1][j];
                if(s[i - 1] == t[j - 1])
                    dp[i][j] += dp[i - 1][j - 1];
            }

        return dp[s.size()][t.size()];
    }
};

int main() {

    string S1 = "rabbbit";
    string T1 = "rabbit";
    cout << Solution().numDistinct(S1, T1) << endl;
    // 3

    // ---

    string S2 = "babgbag";
    string T2 = "bag";
    cout << Solution().numDistinct(S2, T2) << endl;
    // 5

    return 0;
}

/// Source : https://leetcode.com/problems/distinct-subsequences/description/
/// Author : liuyubobobo
/// Time   : 2018-04-23

#include <iostream>
#include <string>
#include <vector>

using namespace std;


/// Dynamic Programming
/// Time Complexity: O(s * t)
/// Space Complexity: O(t)
class Solution {
public:
    int numDistinct(string s, string t) {

        vector<int> dp(t.size() + 1, 0);
        dp[0] = 1;

        for(int i = 1 ; i <= s.size() ; i ++)
            for(int j = t.size() ; j >= 1 ; j --)
                if(s[i - 1] == t[j - 1])
                    dp[j] += dp[j - 1];


        return dp[t.size()];
    }
};


int main() {

    string S1 = "rabbbit";
    string T1 = "rabbit";
    cout << Solution().numDistinct(S1, T1) << endl;
    // 3

    // ---

    string S2 = "babgbag";
    string T2 = "bag";
    cout << Solution().numDistinct(S2, T2) << endl;
    // 5

    return 0;
}