Dory's Phonebook
Background
Dory suffers from short term memory loss. Telephone numbers are one of the greatest mysteries to her.Whenever she wants to call her friend Marlin she discovers that she can hardly remember his name. Because words are not that hard (she can even speak foreign languages) we should help her in translating phone numbers to words.
We want to use a mapping for encoding telephone numbers by words, so that it becomes easier to remember the numbers.
Problem
The following mapping from letters to digits is given:
E JNQ RWX DSY FT AM CIV BKU LOP GHZ
e jnq rwx dsy ft am civ bku lop ghz
0 1 2 3 4 5 6 7 8 9
Your task is writing a program that finds, for a given phone number, all possible encodings by words,and prints them sorted in alphabetical/lexicographical order. A phone number is an arbitrary(!) string of dashes - , slashes / and digits. The dashes and slashes will not be encoded. The words are taken from a dictionary which is given as an ASCII file (one word per line). Every encoding that is possible from this dictionary and that matches the phone number exactly shall be printed. The words in the dictionary contain letters (capital or lowercase), dashes - and double quotes " . For the encoding only the letters are used, but the words must be printed in exactly the form given in the dictionary. Leading non-letters do not occur in the dictionary. Encodings of phone numbers can consist of a single word or of multiple words separated by spaces.
The first line contains the number of scenarios.
Every scenario starts with a line containing the number of words in the dictionary. Following are the words in the dictionary, one per line. Next comes the number of phone numbers, which follow then one per line.
All words in the dictionary and all phone numbers have at most 50 characters. The number of words in the dictionary is limited to 75000, the number of phone numbers per scenario is less than 1000.
For each scenario first output a line "Scenario #i:" where i is the number of the scenario starting with 1. Then you have to work through the phone numbers in the given order. For every possible encoding, print the phone number followed by a colon, a single(!) space, and the encoding on one line; trailing spaces are not allowed. For one phone number sort the different encodings lexicographically/alphabetically (that means based on the ASCII-values of the characters, so case matters). If there is no encoding for a phone number at all, print the phone number, followed by a single space and the string "cannot be encoded.". Terminate each scenario with a blank line.
2 12 an Bo" bo"s da je jemand mir Mix Mixer so Tor Torf 4 112 5624-82 0721/608-4067 10/783--5 5 jrd j rd jr d 1 12312312312312312312312312312312312312312312399
Scenario #1: 112 cannot be encoded. 5624-82: Mix Tor 5624-82: mir Tor 0721/608-4067 cannot be encoded. 10/783--5: je Bo" da Scenario #2: 12312312312312312312312312312312312312312312399 cannot be encoded.
Submit