Given a string of digits, determine the number of distinct ways to partition the string into valid codes, where each code is either a single digit (1-9) or a two-digit number (10-26). Codes with leading zeros or numbers outside the valid range are not allowed. Return the total number of valid decoding ways. If no valid decoding exists, return 0.
Example 1
Input: "3012"
Output: 0
Explanation: No valid decoding because 30 is not a valid code and 0 cannot be decoded alone.
Example 2
Input: "1234"
Output: 3
Explanation: Possible decodings: (1,2,3,4), (12,3,4), (1,23,4).
Example 3
Input: "110"
Output: 1
Explanation: Only (11,0) is invalid, but (1,10) is valid.
Constraints
Case 1
Input: "1001"
Expected: 0
Case 2
Input: "27"
Expected: 1
Case 3
Input: "210"
Expected: 1
Case 4
Input: "2222"
Expected: 5
Case 5
Input: "101"
Expected: 1