String Dynamic Programming Tabulation
Intermediate Level

Implement the decodeWaysCount method that counts how many ways a digit string can be decoded.

The input contains a string digits made of numeric characters. Each number from 1 to 26 can represent a letter, where 1 is A, 2 is B, and 26 is Z.

Your task is to return how many different valid ways the complete string can be decoded. A single 0 cannot be decoded by itself, but it can be part of 10 or 20.

Example 1
Input:
digits (string) = 12
Return:
(int) 2
Example 2
Input:
digits (string) = 226
Return:
(int) 3
Example 3
Input:
digits (string) = 6
Return:
(int) 0

Use dynamic programming where each position stores the number of ways to decode the prefix ending there.

At every position, check the last one digit and the last two digits. A one-digit value is valid if it is from 1 to 9. A two-digit value is valid if it is from 10 to 26.

Add the number of ways from the matching previous position for every valid choice. If the string starts with 0, there are no valid decodings.

Pseudocode:

function decodeWaysCount(digits):
    n = length(digits)
    if n == 0 or digits[0] == '0':
        return 0
    dp = array of n + 1 values filled with 0
    dp[0] = 1
    dp[1] = 1
    for i from 2 to n:
        oneDigit = digits[i - 1]
        twoDigits = number formed by digits[i - 2] and digits[i - 1]
        if oneDigit is between '1' and '9':
            dp[i] = dp[i] + dp[i - 1]
        if twoDigits is between 10 and 26:
            dp[i] = dp[i] + dp[i - 2]
    return dp[n]
Run your code to see the result.