Distinct Subsequences DP accepted code


  • 0
    V

    '''
    class Solution {
    public:
    int numDistinct(string s, string t) {
    int ssz = s.size();
    int tsz = t.size();
    if (ssz == 0 || tsz == 0 || ssz < tsz) return 0;

        int count[tsz+1][ssz+1]; 
        
        for (int m = 0; m < ssz + 1; m++) count[tsz][m] = 1;
        for (int n = 0; n < tsz; n++) count[n][ssz] = 0;       
        for (int m = tsz - 1; m >= 0; m--) {
            for (int n = ssz - 1; n >= 0; n--) {
                if (s[n] == t[m]) {
                    count[m][n] = count[m+1][n+1] + count[m][n+1];                                       
                } else count[m][n] = count[m][n+1];
            }
        }
        return count[0][0];
    }
    

    };
    '''


Log in to reply
 

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