PROBLEM STATEMENT
We can encode the letters of the alphabet by assigning a number to each letter.
The number given to a particular letter will work by the following system:
1) The letter 'A' is given the value 0
2) Every letter after 'A' is given a value one higher than the letter that
immediately precedes it in the alphabet
3) Values corresponding to a letter never have leading zeros
For example, in this system 'A' = 0, 'B' = 1, 'E' = 4, 'H' = 7, 'R' = 17, and
'Z' = 25.
We can encode a string by replacing each letter with its numerical value. For
example, the string "ABBA" would encode to "0110", and the string "RAZE" would
encode to "170254". Since many letters encode to double digit values, a
problem occurs when trying to decode an encoded string. For example, the
string "1717" could decode to "BHBH", "BHR", "RBH", or "RR". Given an encoded
string you will return how many possible ways there are to decode it.
Create a class BadCoding that contains the method numDecode, which takes a
String encoded, and returns an int representing the number of ways to decode
the string.
DEFINITION
Class: BadCoding
Method: numDecode
Parameters: String
Returns: int
Method signature (be sure your method is public): int numDecode(String encoded);
NOTES
- This problem pretends lowercase letters do not exist so they do not play a
role in the encoding/decoding process
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- encoded will have length between 1 and 20 inclusive
- encoded will only contain characters in the string "0123456789" (quotes for
clarity)
EXAMPLES
1) encoded = "99999"
The only possible decoded string is "JJJJJ".
Method returns 1.
2) encoded = "9"
The only possible decoded string is "J".
Method returns 1.
3) encoded = "1111".
Possible decoded strings are "BBBB","LBB","BLB","BBL", and "LL".
Method return 5.
4) encoded = "00010".
Possible decoded strings are "AAABA" and "AAAK".
Method returns 2.
5) encoded = "1579123124"
Method returns 18.
6) encoded = "11111111111111111111"
Method returns 10946.