LeetCode #115 Distinct Subsequen

Given two strings s and t, return the number of distinct subsequences of s which equals t.

A string's subsequence is a new string formed from the original string by deleting some (can be none) of the characters without disturbing the remaining characters' relative positions. (i.e., "ACE" is a subsequence of "ABCDE" while "AEC" is not).

It is guaranteed the answer fits on a 32-bit signed integer.

 

Example 1:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from S.
rabbbit
rabbbit
rabbbit
Example 2:

Input: s = "babgbag", t = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
babgbag
babgbag
babgbag
babgbag
babgbag
 

Constraints:

1 <= s.length, t.length <= 1000
s and t consist of English letters.

/**
* Abstract: to be added later...
*/
#ifdef TEST
#define R 7
#else
#define R 128
#endif

int numDistinct(char * s, char * t) {
    if (t == NULL || s == NULL || strlen(t) == 0 || strlen(s) == 0) return 0;
    int num = 0;
    int n = strlen(s);
    int m = strlen(t);

    //cal idx
    int **idx = (int**)malloc(R * sizeof(int*));
    int **map = (int**)malloc(R * sizeof(int*));
    int *idxi = (int*)malloc(R * sizeof(*idxi));
    int **inv = (int**)malloc(R * sizeof(int*));
    int *cn = (int*)malloc(R * sizeof(*cn));

    for (int c = 0; c < R; c++) { 
        idxi[c] = cn[c] = 0;
        idx[c] = (int*)malloc(n * sizeof(int));
        inv[c] = (int*)malloc(n * sizeof(int));
        map[c] = (int*)malloc(n * sizeof(int));
        for (int i = 0; i < n; i++) { idx[c][i] = map[c][i] = inv[c][i] = -1; }
    }
    for (int i = 0; i < n; i++) {
#ifdef TEST
        char c = s[i] - 'a';
#else
        char c = s[i];
#endif
        map[c][cn[c]] = i;
        inv[c][i] = cn[c];
        cn[c]++;
        while (idxi[c] < i) { idx[c][idxi[c]++] = i; }
    }
    if (m == 1) { return cn[t[0]]; }

#ifdef TEST
    printf("map:\n");
    for (int c = 0; c < R; c++) {
        for (int i = 0; i < n; i++) {
            printf("%i%s", map[c][i], i == n - 1 ? "\n" : " ");
        }
    }
    printf("\n");
    printf("idx:\n");
    for (int c = 0; c < R; c++) {
        for (int i = 0; i < n; i++) {
            printf("%i%s", idx[c][i], i == n - 1 ? "\n" : " ");
        }
    }
    printf("\n");

    printf("inv:\n");
    for (int c = 0; c < R; c++) {
        for (int i = 0; i < n; i++) {
            printf("%i%s", inv[c][i], i == n - 1 ? "\n" : " ");
        }
    }
#endif

    long **dp = (int**)malloc(m * sizeof(long*));//dp[i][j] number of substr when t[i] is matched to s[j]
    for (int i = 0; i < m; i++) { 
        dp[i] = (long*)malloc(n * sizeof(long));
        for (int j = 0; j < n; j++) { dp[i][j] = 0; }
    }

#ifdef TEST
    char c = t[m - 1] - 'a';
#else
    char c = t[m - 1];
#endif
    for (int i = 0; i < cn[c]; i++) { dp[m - 1][map[c][i]] = cn[c] - inv[c][map[c][i]]; }

#ifdef TEST
    for (int i = 0; i < n; i++) { printf("%s%i%s", i == 0 ? "dp:\n" : "", dp[m - 1][i], i == n - 1 ? "\n" : " "); }
#endif

        for (int i = m - 2; i >= 0; i--) {
#ifdef TEST
            char c = t[i] - 'a';
#else
            char c = t[i];
#endif
            long cdp = 0;
            for (int j = cn[c] - 1; j >= 0; j--) {

#ifdef TEST
            char nc = t[i + 1] - 'a';
#else
            char nc = t[i + 1];
#endif
            if (idx[nc][map[c][j]] != -1) {
                dp[i][map[c][j]] += cdp + dp[i + 1][idx[nc][map[c][j]]];
                cdp = dp[i][map[c][j]];
            }
        }
    }

#ifdef TEST
    printf("dp:\n");
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            printf("%i%s", dp[i][j], j == n - 1 ? "\n" : " ");
        }
    }
#endif
    

#ifdef TEST
    return dp[0][map[t[0] - 'a'][0]];
#else
    return dp[0][map[t[0]][0]];
#endif
}