Check the equality for each subset of a string S against the target T and return a count

Question

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.

Answer 1

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.