Given a string of digits, determine the number of valid ways to partition the string into substrings, where each substring represents an integer in the range [1, 26] (inclusive) and does not have leading zeros. Return the total number of valid decoding ways. If the string cannot be decoded in any valid way, return 0.
Example 1
Input: 3172
Output: 2
Explanation: Possible decodings: (3,1,7,2) and (3,17,2)
Example 2
Input: 101
Output: 1
Explanation: Possible decoding: (10,1)
Example 3
Input: 230
Output: 0
Explanation: No valid decoding due to 0.
Constraints
Case 1
Input: '1234'
Expected: 3
Case 2
Input: '110'
Expected: 1
Case 3
Input: '301'
Expected: 0
Case 4
Input: '27'
Expected: 1
Case 5
Input: '1001'
Expected: 0