Data-Structures-and-Algorithms/digit_dp.py at main · codemistic/Data-Structures-and-Algorithms · GitHub

Name: Data-Structures-and-Algorithms/digit_dp.py at main · codemistic/Data-Structures-and-Algorithms · GitHub
Rating: 4.6 (7925 reviews)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Problem Link -: https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
# Problem -: Numbers At Most N Given Digit Set
# Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.
# Return the number of positive integers that can be generated that are less than or equal to a given integer n.


# Python Digit DP Solution
defatMostNGivenDigitSet(self, D: List[str], N: int) ->int:
D=list(map(int, D))
N=list(map(int, str(N)))

@functools.lru_cache(None)
defdp(i, isPrefix, isBigger):
ifi==len(N):
returnnotisBigger
ifnotisPrefixandnotisBigger:
return1+len(D) *dp(i+1, False, False)
return1+sum(dp(i+1, isPrefixandd==N[i], isBiggeror (isPrefixandd>N[i])) fordinD)

returndp(0, True, False) -1