Google Code Jam Practice Problem – T9 Spelling

Problem

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.

Old_Phone

package avdongre.google.code.jam;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Solution {
	static Map<Character, String> keyToNumberMap = new HashMap<Character, String>();
	static Map<Character, Integer> keyOnSameButtton = new HashMap<Character, Integer>();

	static {
		keyToNumberMap.put('a', "2");
		keyToNumberMap.put('b', "22");
		keyToNumberMap.put('c', "222");

		keyToNumberMap.put('d', "3");
		keyToNumberMap.put('e', "33");
		keyToNumberMap.put('f', "333");

		keyToNumberMap.put('g', "4");
		keyToNumberMap.put('h', "44");
		keyToNumberMap.put('i', "444");

		keyToNumberMap.put('j', "5");
		keyToNumberMap.put('k', "55");
		keyToNumberMap.put('l', "555");

		keyToNumberMap.put('m', "6");
		keyToNumberMap.put('n', "66");
		keyToNumberMap.put('o', "666");

		keyToNumberMap.put('p', "7");
		keyToNumberMap.put('q', "77");
		keyToNumberMap.put('r', "777");
		keyToNumberMap.put('s', "7777");

		keyToNumberMap.put('t', "8");
		keyToNumberMap.put('u', "88");
		keyToNumberMap.put('v', "888");

		keyToNumberMap.put('w', "9");
		keyToNumberMap.put('x', "99");
		keyToNumberMap.put('y', "999");
		keyToNumberMap.put('z', "9999");

		keyToNumberMap.put(' ', "0");

		keyOnSameButtton.put('a', 1);
		keyOnSameButtton.put('b', 1);
		keyOnSameButtton.put('c', 1);

		keyOnSameButtton.put('d', 2);
		keyOnSameButtton.put('e', 2);
		keyOnSameButtton.put('f', 2);

		keyOnSameButtton.put('g', 3);
		keyOnSameButtton.put('h', 3);
		keyOnSameButtton.put('i', 3);

		keyOnSameButtton.put('j', 4);
		keyOnSameButtton.put('k', 4);
		keyOnSameButtton.put('l', 4);

		keyOnSameButtton.put('m', 5);
		keyOnSameButtton.put('n', 5);
		keyOnSameButtton.put('o', 5);

		keyOnSameButtton.put('p', 6);
		keyOnSameButtton.put('q', 6);
		keyOnSameButtton.put('r', 6);
		keyOnSameButtton.put('s', 6);

		keyOnSameButtton.put('t', 7);
		keyOnSameButtton.put('u', 7);
		keyOnSameButtton.put('v', 7);

		keyOnSameButtton.put('w', 8);
		keyOnSameButtton.put('x', 8);
		keyOnSameButtton.put('y', 8);
		keyOnSameButtton.put('z', 8);

		keyOnSameButtton.put(' ', 9);

	}

	private static String solve(String nextLine) {
		char[] nextLineCharArray = nextLine.toCharArray();
		char previous = nextLineCharArray[0];
		StringBuilder sb = new StringBuilder();
		sb.append(keyToNumberMap.get(previous));
		for (int i = 1; i < nextLineCharArray.length; i++) {
			char current = nextLineCharArray[i];
			if (keyOnSameButtton.get(previous) == keyOnSameButtton.get(current)) {
				sb.append(" ");
			}
			previous = current;
			sb.append(keyToNumberMap.get(previous));
		}
		return sb.toString();
	}

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		// number of test cases
		int N = Integer.parseInt(stdin.nextLine());
		for (int i = 0; i < N; i++) {
			System.out.println("Case #" + (i + 1) + ": "
					+ solve(stdin.nextLine()));
		}
	}

}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s