Количество неубывающей числовой строки, образованной заменой подстановочного знака '?'

Дана строка S размера N , состоящая из цифр и ? , задача состоит в том, чтобы найти количество строк, образованных таким образом, что замена символа '?' с любыми цифрами, чтобы цифры строки стали неубывающими.

Примеры:

Input: S = “1???2”
Output: 4
Explanation:
The string after valid replacements of ‘?’ is 11112, 11122, 11222, 12222. Therefore, the count of such string is 1.

Input: S = “2??43?4”
Output: 0

Подход: Данную проблему можно решить, заменив '?' со всеми возможными допустимыми комбинациями цифр, используя рекурсию, и сохраните перекрывающиеся подзадачи в таблице dp[]. Выполните следующие шаги, чтобы решить данную проблему:

• Инициализируйте 2D-массив, скажем, dp[][] таким образом, что dp[i][j] будет обозначать возможное количество допустимых строк, имеющих длину i и между двумя числами, разность конечных точек которых равна j . Как разные сегменты, содержащие ? независимы друг от друга. Таким образом, общее количество будет произведением всех вариантов, доступных для каждого сегмента.
• Инициализируйте dp[][] как -1.
• Объявите три переменные L как 0 , R как 9 , cnt , так что L обозначает левый предел сегмента, R обозначает правый предел сегмента, а cnt обозначает длину непрерывного '?' персонажи.
• Пусть общее количество будет сохранено в переменной, скажем , как 1 .
• Определите функцию решения , которая будет рекурсивно вычислять значения узлов dp . Функция решения будет принимать два аргумента (len, gap) , len будет обозначать общую длину непрерывного '?' а разрыв будет обозначать разницу между конечными точками этого сегмента как:
  • Выполните итерацию для каждого возможного пробела и пересчитайте ответ с помощьюsolve(len — 1, gap — i) .
  • Вернуть ответ, полученный от функции решения после заполнения узла dp[len][gap] .
• Переберите каждый символ в строке и выполните следующие шаги:
  • Если текущий символ '?' затем увеличивает переменную cnt .
  • Если текущий символ не является числом, измените правый предел, т.е. R на текущий символ, т.е. R = S[i] – '0' .
  • Умножьте результат, вычисленный рекурсивной функциейsolve (cnt,R – L) .
• После выполнения вышеуказанных шагов выведите значение ans как результирующее количество сформированных строк.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*10)
Вспомогательное пространство: O (N * 10)