Задача: 902. Numbers At Most N Given Digit Set
Сложность: hard

Дан массив цифр, отсортированный в неубывающем порядке. Вы можете записывать числа, используя каждый digits[i] столько раз, сколько захотите. Например, если digits = ['1','3','5'], мы можем записать такие числа, как '13', '551' и '1351315'. Возвращает количество положительных целых чисел, которые могут быть сгенерированы и которые меньше или равны заданному целому числу n.

Пример:

Input: digits = ["1","3","5","7"], n = 100
Output: 20

👨‍💻 Алгоритм:

1⃣Преобразовать заданное число n в строку для удобного доступа к каждой цифре.

2⃣Реализовать рекурсивную функцию для генерации всех возможных чисел с использованием цифр из массива digits и сравнения с n.

3⃣Начать с каждой цифры в digits и рекурсивно строить числа, отслеживая количество подходящих чисел.

😎 Решение:

class Solution {
    func atMostNGivenDigitSet(_ digits: [String], _ n: Int) -> Int {
        let s = String(n)
        let K = s.count
        var dp = [Int](repeating: 0, count: K + 1)
        dp[K] = 1

        for i in stride(from: K - 1, through: 0, by: -1) {
            for d in digits {
                let sc = s[s.index(s.startIndex, offsetBy: i)]
                if d < String(sc) {
                    dp[i] += Int(pow(Double(digits.count), Double(K - i - 1)))
                } else if d == String(sc) {
                    dp[i] += dp[i + 1]
                }
            }
        }

        var total = dp[0]
        for i in 1..<K {
            total += Int(pow(Double(digits.count), Double(i)))
        }

        return total
    }
}

Ставь 👍 и забирай 📚 Базу знаний