tgoop.com/yeahub_go_backend/92
Last Update:
#ЛитКод
Задача: 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
Создайте массив dp, где dp[i] представляет количество способов декодирования подстроки s[0:i]. Установите начальные значения dp[0] = 1 (пустая строка имеет один способ декодирования).
Используйте цикл для обхода строки и вычисления количества способов декодирования для каждого символа, включая обработку символа '*'.
Поскольку количество способов декодирования может быть большим, вычисляйте результаты по модулю 10^9 + 7.
package main
import (
"fmt"
)
func numDecodings(s string) int {
const MOD = 1000000007
n := len(s)
dp := make([]int, n+1)
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]
}
