Krdytkyu

I wrote the following code to solve this leetcode problem:

var numDistinct = function(s, t) {

    if (!s.length) return +(!t.length);

    let res = 0;

    for (let seq of subseq(s)) res += +(t===seq);

    return res; 

};

var subseq = function(a) {

    if (a.length==1) return [a[0], ''];

    let subsets = subseq(a.substr(0, a.length-1));

    let n = subsets.length;

    for (let i=0; i < n; i++) {

       subsets.push(subsets[i]+a[a.length-1]);

    }

    return subsets;

};

Obviously, this code is not efficient, as it generates each of $2^n$ subsets of the string s and checks each one for equality against t.

I would much appreciate it if someone could explain how to improve this solution using memoization. I am aware that there is a dynamic programming solution. I am more interested in learning how to extend this easy-to-understand solution into something more efficient by using a memo table. Any and all help would be graciously appreciated.

I'd just like to point out, that the code IMHO has far too many "length optimizations". Just take the first line:

if (!s.length) return +(!t.length);

I've been a JS developer for over 20 years and I couldn't say off the top of my head what + does to a boolean. It would be much more readable as:

if (s.length === 0) {

  return (t.length === 0) ? 1 : 0;

}

Also a comment why these are the correct return values would be very helpful.