With the advent of text messaging on cell phones, a new method for typing has evolved, called T9. The way T9 works is it has a dictionary of words, where each letter is mapped to a number 2-9. The number-letter mappings are fixed, and are printed on the number keys of the phone. For example, 2 corresponds to 'a', 'b', and 'c'. A word is defined as a sequence of lowercase letters. Since most words use different digits for their characters, it is possible to determine which word a user is typing by matching the digit sequence to the letter sequence. Below are all the mappings for the characters used in the problem:
2 - abc
3 - def
4 - ghi
5 - jkl
6 - mno
7 - pqrs
8 - tuv
9 - wxyz
# - <space>
0 - <next word>
So for example, to type "hello world", you would press "43556#96753". A conflict arises when two words have the same digit sequence. So for example, "the" and "tie" both have the same digit sequence - "843". The way T9 handles these conflicts is to display the word that comes first alphabetically. Then, if the word isn't desired, the user must press 0 to get the next word alphabetically, and repeat until the desired word is shown. If the user wishes to enter another word, he/she presses # to insert a space and starts entering the next word. So to input "the tie", you would type "843#8430". It is illegal to press a non-zero digit immediately after pressing '0', the only legal keys you can press after pressing '0' are '0' and '#'.
You will be given a String[] messages, which consists of messages you are to type into your cell phone. messages will only contain spaces and words made entirely of lowercase letters. Assume that the words contained in all of the messages are exactly the words contained in the T9 dictionary. Return a String[] where each element i contains the numeric keypresses you would have to type for element i of messages. Note that messages do not necessarily have to contain words, and can contain sequences of multiple spaces which must be preserved.
|