Numbers At Most N Given Digit Set LeetCode solution in Python

1
class Solution:
2
    def atMostNGivenDigitSet(self, digits, n):
3
        cache = {}
4
        target = str(n)
5

6
        def helper(idx, isBoundary, isZero):
7
            if idx == len(target):
8
                return 1
9
            if (idx, isBoundary, isZero) in cache:
10
                return cache[(idx, isBoundary, isZero)]
11

12
            res = 0
13
            if isZero and idx != len(target) - 1:
14
                res += helper(idx + 1, False, True)
15
            for digit in digits:
16
                if isBoundary and int(digit) > int(target[idx]):
17
                    continue
18
                res += helper(
19
                    idx + 1,
20
                    True if isBoundary and digit == target[idx] else False,
21
                    False,
22
                )
23

24
            cache[(idx, isBoundary, isZero)] = res
25
            return res
26

27
        return helper(0, True, True)