Untitled
unknown
plain_text
8 months ago
831 B
5
Indexable
Never
class Solution { public: vector<vector<long long>> dp; int numDistinct(string s, string t) { long long m = s.size(); long long n = t.size(); dp.assign(m+1, vector<long long>(n+1,-1)); // doing +1 as working with 0 index is hard // same logic as when doing for LCS // base case for(long long j=0; j<=n; j++){ dp[m][j] = 0; // i == m, so return 0 } for(long long i=0; i<=m; i++){ dp[i][n] = 1; // j == n, so return 1 } for(long long i=m-1; i>=0; i--){ for(long long j=n-1; j>=0; j--){ dp[i][j] = dp[i+1][j]; if(s[i] == t[j]){ dp[i][j] += dp[i+1][j+1]; } } } return dp[0][0]; } };
Leave a Comment