Подсчитайте возможное декодирование заданной последовательности цифр со скрытыми символами

Дана строка S , содержащая цифры и символ '*', т.е. скрытый символ, задача состоит в том, чтобы найти количество способов декодирования этого скрытого символа данной строки.

Поскольку ответ может быть очень большим, верните его по модулю 10 ⁹ +7.

A string containing letters from A-Z can be encoded into numbers using the following mapping:

‘A’ -> “1” 
‘B’ -> “2” 
‘C’ -> “3” 
‘D’ -> “4” 
… 
… 
‘Z’ -> “26” 
Note: Characters including 0 are not included in the problem like (J → 10).

Примеры:

Input: s = “*”
Output: 9
Explanation: The encoded message can represent any of the encoded messages “1”, “2”, “3”, “4”, “5”, “6”, “7”, “8”, or “9”.
Each of these can be decoded to the strings “A”, “B”, “C”, “D”, “E”, “F”, “G”, “H”, and “I” respectively.
Hence, there are a total of 9 ways to decode “*”.

Input: s = “1*”
Output: 18
Explanation: The encoded message can represent any of the encoded messages “11”, “12”, “13”, “14”, “15”, “16”, “17”, “18”, or “19”.
Each of these encoded messages have 2 ways to be decoded (e.g. “11” can be decoded to “AA” or “K”).
Hence, there are a total of 9 × 2 = 18 ways to decode “1*”. 

Подход:

Эту проблему можно решить, заметив, что любое постоянное число может быть либо декодировано в символ, который является однозначной цифрой, либо может быть декодировано в двузначное число, если (i-1)-й символ равен «1» или ( i-1)-й символ равен «2», а i -й символ находится в диапазоне от 1 до 6. Следовательно, текущее состояние зависит от предыдущего состояния, и для решения проблемы можно использовать динамическое программирование. Выполните следующие шаги, чтобы решить проблему:

1. Пусть dp[i] представляет количество способов декодирования символов строки от 0 до i .

2. Если i -й символ '*':

• dp[i] = dp[i-1]*9 , учитывая , что '*' может быть от 1 до 9 , и он считается отдельным символом.
• Теперь, если объединить символы i и i-1 , тогда
  • Если (i-1)-й символ равен «*», то два «**» вместе могут образовать 15 возможных символов (например, 13 образуют символ «M»), поэтому мы добавляем 15 × dp[i-2] к dp[ я] .
  • Если (i-1)-й символ равен «1», то dp[i] = dp[i] + 9×dp[i-2] , поскольку возможные символы, которые можно декодировать, будут от 11 до 19 (от K до S).
  • Если (i-1)-й символ равен «2», то dp[i] = dp[i] + 6×dp[i-2] , так как он может принимать значения от 21 до 26.

3. Если i -й символ не '*':

• dp[i] = dp[i] + dp[i-1], рассматривая только i -й символ как число.
• Теперь, если возможно объединить (i-1)-й символ и i -й символ вместе, добавьте dp[i-2] к dp[i].

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

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

Дальнейшая оптимизация пространства

При внимательном рассмотрении приведенного выше кода видно, что значение dp[i] находится с использованием dp[i-1] и dp[i-2] . Таким образом, для дальнейшей оптимизации пространства вместо создания массива dp длины N мы можем использовать три переменные — вторую (хранит значение dp[i] ), первую (хранит значение dp[i-2] ), и temp (сохраняет значение dp[i-1] ). Итак, найдя значение second(dp[i]) , измените first = temp и temp = second , а затем снова вычислите значение second(dp[i]) с использованием переменных first и temp .

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