T9Spelling - GCJ 2010 (Africa)

Posted on March 23, 2010

Below is a problem from the qualification round of 'Google Code Jam 2010 - Africa':


The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ' ' should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.


The first line of input gives the number of cases, N. N test cases follow. Each case is a line of text formatted as:


Each message will consist of only lowercase characters a-z and space characters ' '. Pressing zero emits a space.


For each test case, output one line containing "Case #x: " followed by the message translated into the sequence of keypresses.


1 ≤ N ≤ 100.

Small dataset

1 ≤ length of message in characters ≤ 15.

Large dataset

1 ≤ length of message in characters ≤ 1000.

Sample Input

foo bar
hello world


Case #1: 44 444
Case #2: 999337777
Case #3: 333666 6660 022 2777
Case #4: 4433555 555666096667775553

There's also a pictorial representation of the problem statement, which I didn't attach to this post. If you want, you can check the link: GCJ 2010 - T9Spelling

The solution for the above problem is pretty easy. Below is my Java solution:

The solution for the above problem can be coded in a couple of other creative ways, but the above solution is fast and works good enough, although it has a trade-off in memory complexity (in the form of HashMap).

Blog Categories
The views expressed on this blog are my personal views and do not reflect the views of my employer or campaigns I am supporting.

All sample code is provided for illustrative purposes only. These examples have not been thoroughly tested under all conditions. The writer therefore, cannot guarantee or imply reliability, serviceability, or function of these programs.

All programs contained herein are provided to you "AS IS" without any warranties of any kind. The implied warranties of non-infringement, merchantability and fitness for a particular purpose are expressly disclaimed.