How many ways to decode a trade-ticket code

Question

A ticketing system encodes each order type as a number 1..26 (A=1, ..., Z=26) and concatenates the digits with no separators. Given the raw digit string, count how many distinct decodings are possible.

"226" -> 3      # "2 2 6" (BBF), "22 6" (VF), "2 26" (BZ)
"06"  -> 0      # no code starts with 0

Return the number of valid decodings. A 0 can only appear as the second digit of 10 or 20.

Accepted Answer

This is a Fibonacci-shaped count. Let dp[i] be the number of ways to decode the first i digits. To extend by one digit, the last digit can stand alone if it is not '0' (add dp[i-1]), and the last two digits can form one code if they read as 10..26 (add dp[i-2]). We only need the two previous counts, so track them in scalars. Tracing "226": after the second digit cur = 2 ("2 2" and "22"); after the third cur = 3. For "100" the middle step gives 1 way ("10"), but the trailing "00" is undecodable, so the result is 0. Time O(n), space O(1). Edge cases: leading '0' returns 0; a lone '0' anywhere t…

How many ways to decode a trade-ticket code

Your answer

More Coding questions