Solutions

# Variation of n-th staircase with n = [1, 2] steps. Top-down or bottom-up DP.
# dp

# DP bottom-up - O(n) time, O(n) space (can be O(1) using 2 vars)
def numDecodings1(s: str) -> int:
    if not s:
        return 0

    # dp[i] = the number of ways to decode the string s[0: i + 1]
    dp = [0] * (len(s) + 1) # +1 to handle the base case of empty string, and also because right side slicer index is exclusive
    dp[0] = 1
    dp[1] = 0 if s[0] == '0' else 1

    for i in range(2, len(s)+1):
        if 0 < int(s[i-1:i]) <= 9:
            dp[i] += dp[i - 1]
        if 10 <= int(s[i-2:i]) <= 26:
            dp[i] += dp[i - 2]

    return dp[-1]
    
# Recursion DP top-down -  O(n) time (w/o DP would be O(2^n)), O(n) space
def numDecodings(s: str) -> int:
    dp = { len(s): 1 } # case len(s): we successfully decoded the entire string

    # dfs(i) = numbers of ways to decode s[i:]
    def dfs(i: int) -> int:
        if i in dp:
            return dp[i]
        if s[i] == '0':
            return 0 # invalid decoding

        res = dfs(i+1)
        if i+2 <= len(s) and 10 <= int(s[i:i+2]) <= 26:
            res += dfs(i+2)

        dp[i] = res
        return res

    return dfs(0)


if __name__ == "__main__":
    assert numDecodings("12") == 2
    assert numDecodings("226") == 3
    assert numDecodings("0") == 0
    assert numDecodings("06") == 0