902.md

902. Numbers At Most N Given Digit Set

Solution 1 (time O(log(n)*k), space O(k))

# Dynamic Programming
class Solution(object):
    def atMostNGivenDigitSet(self, digits, n):
        """
        :type digits: List[str]
        :type n: int
        :rtype: int
        """
        s = str(n)
        k = len(s)
        m = len(digits)
        dp = [[0, 0] for _ in range(k + 1)]
        dp[0][1] = 1
        for i in range(1, k + 1):
            for d in digits:
                if d == s[i - 1]:
                    dp[i][1] = dp[i - 1][1]
                elif d < s[i - 1]:
                    dp[i][0] += dp[i - 1][1]
                else:
                    break
            if i > 1:
                dp[i][0] += m + dp[i - 1][0] * m
        return dp[-1][0] + dp[-1][1]