2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ It seems more like stackoverflow question... \$\endgroup\$ – Dmitry Yaremenko Feb 13 '18 at 7:34
0
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the feedback. Normally, for these 'competitive programming' sites I like to keep the code as short as possible as others submit their code this way and in many cases it's made it quicker to understand a solution. In this case, I agree it may obscure the intention of the code. The reasoning is that only one subset of the empty string matches empty string (the set including the empty string), so return 1 in that scenario. As you can probably tell, it's 'that one annoying edge case'. \$\endgroup\$ – Fahd Ahmed Feb 13 '18 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.