distict_seq_b2u.cc

class Solution {
public:
    int numDistinct(string S, string T) {
        int **mmap = (int **) malloc((S.size() + 1) * sizeof(int *));
        for (int i = 0; i < S.size() + 1; ++i) {
            mmap[i] = (int *) malloc((T.size() + 1) * sizeof(int));
        }
        for (int i = 0; i < S.size() + 1; ++i) {
            mmap[i][0] = 1;
        }
        
        for (int i = 1; i < T.size() + 1; ++i) {
            mmap[0][i] = 0;
        }
        
        for (int i = 1; i < S.size() + 1; ++i) {
            for (int j = 1; j < T.size() + 1; ++j) {
                if (S[i-1] == T[j-1]) {
                    mmap[i][j] = mmap[i-1][j] + mmap[i-1][j-1];
                } else {
                    mmap[i][j] = mmap[i-1][j];
                }
            }
        }
        int temp = mmap[S.size()][T.size()];
        for (int i = 0; i < S.size() + 1; ++i) {
            free(mmap[i]);
        }
        free(mmap);
        return temp;
    }
};