[C] 0ms solution with pruning in DP, space O(n), time O(m*n)


  • 0
    G
    int numDistinct(char* s, char* t) {
        if (!s || !t) return 0;
        const int NS = strlen(s);
        const int NT = strlen(t);
        if (NS < NT) return 0;
        if (NS == NT) return !strcmp(s, t);
        if (!NT) return 0;
    
        int c[NT];
        int i, j, chs, limit;
        for (j = 0; j < NT; j++) c[j] = 0;
        for (i = 0; i < NS; i++) {
            chs = s[i];
            limit = NT - 1;
            if (limit > i) limit = i;
            for (j = limit; j > 0; j--) {
                if (t[j] == chs) c[j] += c[j - 1];
            }
            if (t[0] == chs) c[0]++;
        }
        return c[NT - 1];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.