1
/**
2
 * @param {string} s
3
 * @param {number} k
4
 * @return {number}
5
 */
6
var numberOfArrays = function (s, k) {
7
  var cache = {};
8
  return backtrack(0) % 1000000007;
9
  function backtrack(pos) {
10
    let orignalPos = pos;
11
    if (cache[pos] !== undefined) {
12
      return cache[pos];
13
    }
14
    let count = 0;
15
    let digit = 0;
16
    while (pos < s.length) {
17
      digit = digit * 10 + parseInt(s[pos]);
18
      if (digit <= k && pos + 1 <= s.length - 1 && s[pos + 1] !== "0") {
19
        //If we can call backtrack on next position.
20
        count += backtrack(pos + 1) % 1000000007;
21
      }
22
      if (digit > k) {
23
        break;
24
      }
25
      pos++;
26
    }
27
    if (pos === s.length && digit <= k) {
28
      //If this number became the only digit in the array, for string starting at position orignalPos. This also completed the etire string.
29
      count++;
30
    }
31
    cache[orignalPos] = count;
32
    return count;
33
  }
34
};