1
"""
2
                                "1317"
3
[1, 3, 1, 7]        -> [1] * nums(317, k)
4
[1, 3, 17]
5
[1, 31, 7]
6
[1, 317]
7
[13, 1, 7]          -> [13] * nums(17, k)
8
[13, 17]
9
[131, 7]
10
[1317]
11

12

13
                            "2020"    k = 30
14
[2000] x
15
[2, 020] x
16
[20, 20]
17

18
                            "67890" k = 90
19

20
[6, 7890] x
21
[6, 7, 8, 9, 0] x
22
[6, 7, 8, 90]   OK
23
[6, 78, 90]     OK
24
[67, 8, 90]     OK
25
[67, 89, 0] x
26
[678, 90] x
27
break because 678 > k (90), so neither 678, 6789 would be possible numbers
28

29
"""
30

31

32
class Solution:
33
    def num_arrays(self, s, k, memo):
34
        if not s:
35
            return 0
36
        memo_ans = memo.get(s)
37
        if memo_ans is not None:
38
            return memo_ans
39

40
        num = int(s)
41
        if num <= k:
42
            counter = 1
43
        else:
44
            counter = 0
45

46
        for i in range(len(s) - 1):
47
            # Stop when the number to the right side of the array is greater than k
48
            if int(s[: i + 1]) > k:
49
                break
50
            # Don't count leading zeros
51
            if s[i + 1] == "0":
52
                continue
53
            counter += self.num_arrays(s[i + 1 :], k, memo)
54
        ans = counter % (10**9 + 7)
55
        memo[s] = ans
56
        return ans
57

58
    def numberOfArrays(self, s: str, k: int) -> int:
59
        memo = {}
60
        return self.num_arrays(s, k, memo)