#ЛитКод
Задача: 639. Decode Ways II

Сообщение, содержащее буквы от A-Z, может быть закодировано в цифры с помощью следующего отображения: 'A' -> "1" 'B' -> "2" ... 'Z' -> "26" Чтобы декодировать закодированное сообщение, все цифры должны быть сгруппированы, а затем снова преобразованы в буквы с помощью обратного отображения (может быть несколько способов). Например, "11106" может быть преобразовано в: "AAJF" с группировкой (1 1 10 6) "KJF" с группировкой (11 10 6) Обратите внимание, что группировка (1 11 06) недействительна, поскольку "06" не может быть преобразовано в "F", так как "6" отличается от "06". В дополнение к вышеуказанным преобразованиям кодированное сообщение может содержать символ "*", который может представлять любую цифру от "1" до "9" ("0" исключается). Например, кодированное сообщение "1*" может представлять любое из кодированных сообщений "11", "12", "13", "14", "15", "16", "17", "18" или "19". Декодирование "1*" эквивалентно декодированию любого из кодированных сообщений, которые оно может представлять. Если задана строка s, состоящая из цифр и символов '*', верните количество способов ее декодирования. Поскольку ответ может быть очень большим, верните его по модулю 109 + 7.

Пример:

Input: s = "*"
Output: 9

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

1⃣Инициализация
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).

2⃣Обход строки
Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'.

3⃣Модульное вычисление
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.

😎 Решение:

var numDecodings = function(s) {
    const MOD = 1e9 + 7;
    const n = s.length;
    const dp = new Array(n + 1).fill(0);
    dp[0] = 1;

    for (let i = 1; i <= n; i++) {
        if (s[i - 1] === '*') {
            dp[i] = 9 * dp[i - 1];
        } else if (s[i - 1] !== '0') {
            dp[i] = dp[i - 1];
        }

        if (i > 1) {
            if (s[i - 2] === '*') {
                if (s[i - 1] === '*') {
                    dp[i] += 15 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += 2 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '1') {
                if (s[i - 1] === '*') {
                    dp[i] += 9 * dp[i - 2];
                } else {
                    dp[i] += dp[i - 2];
                }
            } else if (s[i - 2] === '2') {
                if (s[i - 1] === '*') {
                    dp[i] += 6 * dp[i - 2];
                } else if ('0' <= s[i - 1] && s[i - 1] <= '6') {
                    dp[i] += dp[i - 2];
                }
            }
        }

        dp[i] %= MOD;
    }

    return dp[n];
};

👉Новости 👉Платформа