#ЛитКод
Задача:
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];
};👉
Новости 👉
Платформа
