Decode Ways Count

Problem Description

Given a non-empty string containing only digits, write a function to count the number of ways to decode it. A valid decoding follows the mapping: 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. For example, the string '12' can be decoded as 'AB' (1 2) or 'L' (12).

Your task is to implement the function with a dynamic programming approach to efficiently count all possible decodings.

Input

• A string s consisting of digits from '0' to '9'.

Output

• Return the total number of ways to decode the string as an integer.

Constraints

• The input string is non-empty.
• The input string may contain leading zero(s) which might result in invalid decodings.

Example

Input: s = "226"

Output: 3

Explanation:

• The possible decodings are "BZ" (2 26), "VF" (22 6), and "BBF" (2 2 6).

Note

On this day in history, many great innovations remind us that creativity and persistence are key to solving challenging problems. Use a dynamic programming approach to optimize your solution.

Happy coding!