hvJNbI - Online Python3 Interpreter & Debugging Tool

def count_decodings(digits: str) -> int:
    # Отримати довжину вхідного рядка
    n = len(digits)

    # 1. Обробка початкових обмежень
    # Якщо рядок порожній або починається з '0', декодування неможливе.
    if n == 0 or digits[0] == '0':
        return 0

    # Створюємо масив DP. dp[i] - кількість способів для префікса довжиною i
    dp = [0] * (n + 1)

    # 2. Базові випадки
    dp[0] = 1  # Пустий рядок (точка старту)
    dp[1] = 1  # Перша цифра (ми вже перевірили, що вона не '0')

    # 3. Ітерація та застосування рекурентного співвідношення
    for i in range(2, n + 1):
        # i-1 - індекс останньої цифри
        # i-2 - індекс передостанньої цифри

        # --- Варіант 1: Крок на 1 (Одноцифровий) ---
        one_digit = int(digits[i-1:i]) # Отримати останню цифру

        # Умова: цифра має бути від 1 до 9
        if 1 <= one_digit <= 9:
            dp[i] += dp[i-1]

        # --- Варіант 2: Крок на 2 (Двоцифровий) ---
        two_digits = int(digits[i-2:i]) # Отримати дві останні цифри

        # Умова: число має бути від 10 до 26
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]

        # Якщо dp[i] залишається 0, це означає, що на позиції i
        # немає дійсних шляхів (наприклад, "30").
        if dp[i] == 0:
            return 0

    # Результат - кількість способів декодувати весь рядок
    return dp[n]

# Приклади для перевірки:
# print(f"\"121\": {count_decodings('121')}")     # 3
# print(f"\"1234\": {count_decodings('1234')}")   # 3
# print(f"\"230\": {count_decodings('230')}")     # 0