Decode Ways

medium

A message containing letters from A-Z can be encoded into numbers using the mapping 'A' -> "1", 'B' -> "2", … 'Z' -> "26".

To decode an encoded message, all the digits must be grouped and mapped back into letters using the reverse of this mapping. Note that "06" cannot be mapped into 'F', because "6" and "06" are different.

Given a string s containing only digits, return the number of ways to decode it.

Test Cases

Copy an input into the main harness and Run to verify

Input

s = "12"

Expected Output

2

Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Input

s = "226"

Expected Output

3

Explanation: "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Input

s = "06"

Expected Output

0

Explanation: "06" cannot be mapped, because leading zeros are not allowed.

Constraints

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

Hints

Hint 1 — click to reveal

This is Climbing Stairs with validity rules — you take one digit or two.

Hint 2 — click to reveal

A '0' can never stand alone, and a two-digit group is valid only in the range 10 to 26.

Java Compiler