Сложность: hard
Программа должна была напечатать массив целых чисел. Программа забыла напечатать пробелы, и массив напечатан как строка цифр s, и всё, что мы знаем, это что все числа в массиве были в диапазоне [1, k] и в массиве нет ведущих нулей.
Учитывая строку s и целое число k, верните количество возможных массивов, которые могут быть напечатаны как s с использованием упомянутой программы. Так как ответ может быть очень большим, верните его по модулю 10^9 + 7.
Пример:
Input: s = "1000", k = 10000
Output: 1
Explanation: The only possible array is [1000]
👨💻 Алгоритм:
1⃣Создать массив dp размера m + 1, чтобы хранить значения dfs(x).
2⃣Для получения значения dfs(start), если dp[start] не равно нулю, вернуть его значение. Иначе:
Если s[start] == 0, вернуть 0.
Если start = m, вернуть 1.
Инициализировать count = 0, чтобы считать количество возможных массивов.
Перебрать все возможные конечные индексы end, и если s[start ~ end] представляет допустимое число, продолжить рекурсивный вызов dfs(end + 1) и обновить count как count += dfs(end + 1).
Обновить dp[start] значением dfs(start).
3⃣Вернуть dfs(0).
😎 Решение:
class Solution {
let mod = 1_000_000_007
func dfs(_ dp: inout [Int], _ start: Int, _ s: String, _ k: Int) -> Int {
if dp[start] != 0 {
return dp[start]
}
if start == s.count {
return 1
}
if s[s.index(s.startIndex, offsetBy: start)] == "0" {
return 0
}
var count = 0
for end in start..<s.count {
let startIndex = s.index(s.startIndex, offsetBy: start)
let endIndex = s.index(s.startIndex, offsetBy: end + 1)
let currNumber = String(s[startIndex..<endIndex])
if Int(currNumber)! > k {
break
}
count = (count + dfs(&dp, end + 1, s, k)) % mod
}
dp[start] = count
return count
}
func numberOfArrays(_ s: String, _ k: Int) -> Int {
var dp = Array(repeating: 0, count: s.count + 1)
return dfs(&dp, 0, s, k)
}
}Ставь 👍 и забирай 📚 Базу знаний