Decode Ways - Medium Python 1-D Dynamic Programming Interview Problem

A message containing letters A-Z is encoded using the mapping 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26". Given a string s of digits, return the number of ways to decode it.

If there is no valid decoding, return 0.

Example 1

Input: s = "12"
Output: 2
Explanation: "12" can be decoded as "AB" (1, 2) or "L" (12). Two ways.

Example 2

Input: s = "226"
Output: 3
Explanation: "226" can be decoded as "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6). Three ways.

Constraints

1 <= s.length <= 100
s contains only digits
s may contain leading zeros

Hints