Saturday, September 19, 2026

dp[i] = 前 i 个字符的有效解码方式数
      = number of ways to decode s[0..i-1]

选择1 — 单位解码 s[i-1]:
  if s[i-1] != '0':           # '0' 单独无法解码
      dp[i] += dp[i-1]

选择2 — 两位解码 s[i-2..i-1]:
  two = int(s[i-2:i])
  if 10 <= two <= 26:         # 有效范围：10-26
      dp[i] += dp[i-2]

dp[0] = 1   # 空字符串算1种（递推的出发点）
dp[1] = 1 if s[0] != '0' else 0

def numDecodings_brute(s: str) -> int:
    """
    Naive recursion — O(2^n) time, O(n) stack space.
    Don't use in interviews; use to understand the branching structure.
    """
    def dfs(i: int) -> int:
        # Base: consumed all characters successfully
        if i == len(s):
            return 1
        # Dead end: current character is '0', no valid single-digit mapping
        if s[i] == '0':
            return 0

        # Branch 1: decode s[i] as a single character (1-9)
        ways = dfs(i + 1)

        # Branch 2: decode s[i:i+2] as a two-digit number (10-26)
        if i + 1 < len(s):
            two_digit = int(s[i:i+2])
            if 10 <= two_digit <= 26:
                ways += dfs(i + 2)

        return ways

    return dfs(0)

from functools import lru_cache

def numDecodings_memo(s: str) -> int:
    """
    Top-down DP with memoization.
    Identical logic to brute force, but each unique index computed once.
    """
    @lru_cache(maxsize=None)
    def dfs(i: int) -> int:
        if i == len(s):
            return 1
        if s[i] == '0':
            return 0

        ways = dfs(i + 1)  # single-digit decode

        if i + 1 < len(s) and 10 <= int(s[i:i+2]) <= 26:
            ways += dfs(i + 2)  # two-digit decode

        return ways

    return dfs(0)

def numDecodings(s: str) -> int:
    """
    Bottom-up DP — O(n) time, O(n) space.

    dp[i] = number of ways to decode s[0..i-1]

    Recurrence:
      if s[i-1] != '0':           dp[i] += dp[i-1]  (1-digit decode)
      if 10 <= s[i-2:i] <= 26:    dp[i] += dp[i-2]  (2-digit decode)
    """
    n = len(s)
    dp = [0] * (n + 1)

    dp[0] = 1                          # empty string baseline
    dp[1] = 0 if s[0] == '0' else 1   # first char: 1 way unless it's '0'

    for i in range(2, n + 1):
        # --- Option 1: decode the single character s[i-1] ---
        if s[i-1] != '0':              # '0' has no standalone mapping
            dp[i] += dp[i-1]

        # --- Option 2: decode the two-character s[i-2:i] ---
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:      # valid two-digit encoding range
            dp[i] += dp[i-2]

    return dp[n]


# --- Trace: s = "226" ---
#
# dp = [1, 1, 0, 0]   (initialized)
#
# i=2: s[1]='2'  → != '0' → dp[2] += dp[1] = 1
#       s[0:2]="22" → 10<=22<=26 → dp[2] += dp[0] = 1   → dp[2] = 2
#
# i=3: s[2]='6'  → != '0' → dp[3] += dp[2] = 2
#       s[1:3]="26" → 10<=26<=26 → dp[3] += dp[1] = 1   → dp[3] = 3
#
# Answer: 3  ✓  (BBF, BZ, VF)

def numDecodings_optimized(s: str) -> int:
    """
    Space-optimized DP — O(n) time, O(1) space.

    Since dp[i] only depends on dp[i-1] and dp[i-2],
    replace the array with two rolling variables.
    """
    n = len(s)

    prev2 = 1                           # dp[0]: empty string
    prev1 = 0 if s[0] == '0' else 1    # dp[1]: first character

    if n == 1:
        return prev1

    for i in range(2, n + 1):
        curr = 0

        # Single digit
        if s[i-1] != '0':
            curr += prev1

        # Two digit
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            curr += prev2

        # Slide window: prev2 ← prev1, prev1 ← curr
        prev2, prev1 = prev1, curr

    return prev1

def numDecodings_ii(s: str) -> int:
    """
    Decode Ways II — handles '*' wildcard.
    O(n) time, O(1) space. Result mod 10^9 + 7.

    '*' represents any digit in 1-9 (NOT 0).
    """
    MOD = 10**9 + 7
    n = len(s)

    # dp[1] for the first character
    prev2 = 1
    if s[0] == '*':
        prev1 = 9       # '*' can be 1-9 → 9 ways
    elif s[0] == '0':
        prev1 = 0       # '0' alone is never valid
    else:
        prev1 = 1       # any other digit: exactly 1 way

    if n == 1:
        return prev1

    for i in range(2, n + 1):
        curr = 0
        c = s[i-1]   # current character
        p = s[i-2]   # previous character

        # ---- Single-digit decode ----
        if c == '*':
            curr += 9 * prev1      # '*' = 1-9: 9 choices
        elif c != '0':
            curr += prev1          # literal non-zero digit: 1 choice

        # ---- Two-digit decode ----
        if p == '*' and c == '*':
            # "**": 11-19 (9 combos) + 21-26 (6 combos) = 15
            curr += 15 * prev2

        elif p == '*' and c != '*':
            # prev='*', curr=literal digit c
            # "1c" is always valid (10-19, c=0-9)
            # "2c" is valid only if c <= '6' (20-26)
            if c <= '6':
                curr += 2 * prev2  # both "1c" and "2c" work
            else:
                curr += 1 * prev2  # only "1c" works (c>6 → "2c">26)

        elif p != '*' and c == '*':
            # prev=literal digit p, curr='*'
            if p == '1':
                curr += 9 * prev2  # "1*" → 11-19 → 9 ways
            elif p == '2':
                curr += 6 * prev2  # "2*" → 21-26 → 6 ways
            # else p >= '3': "3*" >= 31 > 26, always invalid → +0

        else:
            # Both literal digits: same as LC #91
            two_digit = int(s[i-2:i])
            if 10 <= two_digit <= 26:
                curr += prev2

        curr %= MOD
        prev2, prev1 = prev1, curr

    return prev1