headfirst-js-for-leetcode/115.distinct-subsequences.js at master · chungchi300/headfirst-js-for-leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/*
Involves dynamic programming

var numDistinct = function(S, T) {
    if (S.length < T.length || T.length === 0 || S.length === 0) return 0;
    else if (S == T) return 1;
    else {
        var zero = Array.apply(null, new Array(S.length)).map(Number.prototype.valueOf,0);
        var previous = zero.slice();
        var current  = zero.slice();
        for (var i=0; i < T.length; i++) {
            var sum = 0;
            for (var j=0; j < S.length; j++) {
                if (T[i] === S[j]) {
                    current[j] = (i === 0 ? 1: sum);
                }
                sum += previous[j];
            }
            previous = current.slice();
            current  = zero.slice();
        }
        return previous.reduce(function(a,b) {return a+b});
    }
};

*/
var numDistinct = function(S, T) {
  if (S.length < T.length || T.length === 0 || S.length === 0) return 0;
  else if (S == T) return 1;
  else {
    var zero = Array.apply(null, new Array(S.length)).map(
      Number.prototype.valueOf,
      0
    );
    var previous = zero.slice();
    var current = zero.slice();
    for (var i = 0; i < T.length; i++) {
      var sum = 0;
      for (var j = 0; j < S.length; j++) {
        if (T[i] === S[j]) {
          current[j] = i === 0 ? 1 : sum;
        }
        sum += previous[j];
      }
      previous = current.slice();
      current = zero.slice();
    }
    return previous.reduce(function(a, b) {
      return a + b;
    });
  }
};