PROBLEM LINK:
Author: Parth Trehan
Editorial: Parth Trehan
DIFFICULTY:
SIMPLE-EASY
PREREQUISITES:
Greedy
PROBLEM:
Choose a digit sequence with respect to each alphabet. If any conflict arises on first priority we get the digit sequence of minimum length and on second priority, we the the sequence of smaller number.
EXPLANATION:
Imagine an ITU E 1.161 International Standard mobile keypad. Now, these keypads used to have characters written on them represented by number 2 - number 9 and number 0 was used for space. The keypad can be imagined from below.
2ABC 3DEF
4GHI 5JKL 6MNO
7PQRS 8TUV 9WXYZ
0[space]
Now, the question says that the character configuration represented by each number on the keypad has been shuffled. Now, we have a string inputed and we need to print the sequence of the digits need to be pressed to write than sentence. We need the lexicographically as we as shortest sequence possible. We initialize a hash map of type <character,string>. For each alphabet from A-Z, initialize the hash-map with a very long string e.g. “noinput”. For each of the 8 words (where each word corresponds to the characters present on each number), make a sequence i.e. suppose, we have PTXZ corresponding for number 2 on the keypad, then P can be written as 2, T can be written as 22, X can be written as 222 and Z can be written as 2222. Now, for a character, if newly formed sequence is less in length than the previously stored string, replace it. As we are traversing from 2 - 9, it will by default give us the lexicographically smaller sequence. Obtain such sequence for each character if possible.
Now, we start converting the query string. If the value of a character in the hash-map remains unchanged i.e. “noinput”, then we print “NAN” else we create a new string and similarly we generate a new sequence string.