Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
864 B
8
Indexable
Never
class Solution {
public:
    vector<vector<int>> dp;
    int solve(int i, int j, string s, string t){
        // i is the index for stirng s
        // j is the index for string t

        // base case
        if(j == t.size()) return 1; // as we have reached the end of the string to compare with

        if(i == s.size()) return 0; // as t still has some elements to compare with

        if(dp[i][j] != -1) return dp[i][j];
        if(s[i] == t[j]){
            return dp[i][j] = (solve(i+1, j+1, s, t) + solve(i+1, j, s, t));
            // as the next element can also be same as the current element, we need to add that into our count
        } else {
            return dp[i][j] = solve(i+1, j, s, t);
        }
    }
    int numDistinct(string s, string t) {

        dp.assign(s.size(), vector<int>(t.size(), -1));
        return solve(0,0,s,t);
    }
};
Leave a Comment