218. Decode Ways

A message of digits is encoded with 'A'->1 ... 'Z'->26. Given a digit string s, return the number of ways to decode it. A leading zero or an invalid two-digit group makes that path invalid.

Input: A quoted digit string s.

Output: Integer — number of decodings.

Examples

Input: "12"
Output: 2
Explanation: 'AB' or 'L'.

Input: "226"
Output: 3
Explanation: 'BZ','VF','BBF'.

Input: "06"
Output: 0
Explanation: Leading zero invalid.

Constraints

• 1<=s.length<=100
• digits only

Asked by