Decode Ways

Medium

A message of digits is encoded to letters using the mapping 'A' -> 1, ..., 'Z' -> 26. Given a digit string s, return the number of ways to decode it. The answer fits in a 32-bit integer.

Example 1

Input:  s = "12"
Output: 2
Explanation: "AB" (1 2) or "L" (12).

Example 2

Input:  s = "226"
Output: 3

Example 3

Input:  s = "06"
Output: 0

Constraints

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