(self, D: List[str], N: int)
| 7 | |
| 8 | # Python Digit DP Solution |
| 9 | def atMostNGivenDigitSet(self, D: List[str], N: int) -> int: |
| 10 | D = list(map(int, D)) |
| 11 | N = list(map(int, str(N))) |
| 12 | |
| 13 | @functools.lru_cache(None) |
| 14 | def dp(i, isPrefix, isBigger): |
| 15 | if i == len(N): |
| 16 | return not isBigger |
| 17 | if not isPrefix and not isBigger: |
| 18 | return 1 + len(D) * dp(i + 1, False, False) |
| 19 | return 1 + sum(dp(i + 1, isPrefix and d == N[i], isBigger or (isPrefix and d > N[i])) for d in D) |
| 20 | |
| 21 | return dp(0, True, False) - 1 |