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) =
12Returns (int)
2Example 2
Input
digits (string) =
226Returns (int)
3Example 3
Input
digits (string) =
6Returns (int)
0Use 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]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run