SPOJ ACODE

From Algorithmist
Jump to: navigation, search

394. Alphacode[edit]

Also seen at:

Source: East Central North America 2004

Summary[edit]

Two people want to send coded messages to each other. One possible encoding scheme is to simply replace each letter with its numerical value in the alphabet and then string all the digits together without spaces. Determine the number of possible ways to decode a message encoded this way.

Explanation[edit]

This is a dynamic programming problem.

If we take a single number a, the problem will be in a single state. If you want to add another number b to the problem, the problem could be in one of two states:

  • The two numbers printed one after another, ab
  • The two numbers combined to form a different single number, c (a*10+b)

One or both of the above states may be valid. If the first one remains valid(b\neq 0), the new state is b. If the second remains valid (1\leq c\leq 26) then the state is c. For each of the two valid states, keep track of the previous valid states that lead to it.

Optimizations[edit]

Gotchas[edit]

  • The result is a 64-bit integer - make sure intermediate calculations use that data type.
  • String "110" only has one possible encoding.

Input[edit]

25114
1111111111
3333333333
226210
0

Output[edit]

6
89
1
3

External Links[edit]