Задача: 639. Decode Ways II
Сложность: hard

Сообщение, содержащее буквы от 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.

😎 Решение:

function numDecodings($s) {
    $MOD = 1000000007;
    $n = strlen($s);
    $dp = array_fill(0, $n + 1, 0);
    $dp[0] = 1;

    for ($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 ($s[$i - 1] >= '0' && $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 ($s[$i - 1] >= '0' && $s[$i - 1] <= '6') {
                    $dp[$i] += $dp[$i - 2];
                }
            }
        }

        $dp[$i] %= $MOD;
    }

    return $dp[$n];
}

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