Decode Ways - 数字文字列の復号方法カウント

🎯 ステップバイステップ解説

💻 Python コード実装

LeetCode 形式の Solution クラス。ローリングDP で O(n) 時間 / O(1) 空間を実現。

from __future__ import annotations
from typing import Final


class Solution:
    """
    Decode Ways (LeetCode 91)
    数字文字列を A-Z ('1'-'26') にデコードする方法の総数を返す。

    アルゴリズム:
    - ローリングDP (prev2, prev1) で O(n) 時間 / O(1) 追加メモリ
    - 1桁: '1'..'9' が有効
    - 2桁: '10'..'26' が有効
    - '0' 単独や先頭0は無効
    """

    def numDecodings(self, s: str) -> int:
        """
        Args:
            s: 数字のみから成る文字列（長さ 1..100）

        Returns:
            デコード方法の総数（不能なら 0）

        Complexity:
            Time: O(n), Space: O(1)
        """
        n: Final[int] = len(s)

        # 基底条件: 空文字列は不正
        if n == 0:
            return 0

        # 先頭が '0' ならデコード不能
        first_digit: int = ord(s[0]) - ord('0')
        if first_digit == 0:
            return 0

        # DP初期値:
        # prev2 = dp[-1] = 1 (空文字列の基数)
        # prev1 = dp[0] = 1 (先頭1文字、'1'..'9' が確定)
        prev2: int = 1
        prev1: int = 1

        # 位置 1 から n-1 まで処理
        for i in range(1, n):
            d1: int = ord(s[i]) - ord('0')        # 現在の1桁
            d0: int = ord(s[i - 1]) - ord('0')    # 直前の1桁

            cur: int = 0

            # 遷移1: 1桁が有効 ('1'..'9')
            if 1 <= d1 <= 9:
                cur += prev1

            # 遷移2: 2桁が有効 ('10'..'26')
            two_digit: int = d0 * 10 + d1
            if 10 <= two_digit <= 26:
                cur += prev2

            # どちらも不可 → デコード不能
            if cur == 0:
                return 0

            # ローリング更新
            prev2, prev1 = prev1, cur

        return prev1

📊 視覚的フローチャート

アルゴリズムの処理フロー全体を俯瞰する静的図解。

各位置で1桁・2桁の有効性を判定し、通り数を累積。どちらも不可なら即座に 0 を返す。

⚡ 計算量分析