A message of capital letters was encoded by replacing each letter with its position in the alphabet: A -> "1", B -> "2", ..., Z -> "26". The separators were lost, so a digit string like "121" could have come from "ABA", "AU" or "LA".
Implement num_decodings(s: str) -> int: the number of letter strings that encode to exactly s. Each code is 1–26 written without leading zeros, so "06" is not a valid code for F. Return 0 if s can't be decoded at all.
num_decodings("121") # 3 ABA, AU, LA
num_decodings("2101") # 1 B J A ("21" would leave "01", which is invalid)
num_decodings("30") # 0 "30" and "0" are both invalid codes
Constraints: 1 <= len(s) <= 100, s contains only digits. The count can be large, so return the exact Python int.
Trying every way to split the string is exponential on strings like "1111…"; aim for O(len(s)).
Show hint
The last letter of a decoding comes from either the last digit or the last two digits. Count the decodings of each prefix of s in turn.