115. Distinct Subsequences

https://leetcode.com/problems/distinct-subsequences/

Python

Javascript

var numDistinct = function(s, t) {
    const memo = {};
    
    const dfs = (i, j) => {
        if (!memo.hasOwnProperty(i)) memo[i] = {};
        
        if (j === t.length) return 1;
        if (i === s.length) return 0;
        if (memo[i][j] !== undefined) return memo[i][j];
        
        if (s[i] === t[j]) {
            memo[i][j] = dfs(i + 1, j + 1) + dfs(i + 1, j);
        } else {
            memo[i][j] = dfs(i + 1, j)
        }
        
        return memo[i][j]
    }
    return dfs(0, 0);
};