Description
Predictive text
On a mobile phone (old), a text message word can be created by pressing the digits 2 to 9. For example, to spell the word rake, you press 7 three times, 2 once, 5 twice and 3 twice.
In so-called ‘predictive text’ mode, you will press 7 2 5 3 – each digit once and the phone will try and figure out which word you want. If there are several possibilities, it will allow you to choose the one you want. In this example, possible words are pale, rake, sake and sale. The phone uses a dictionary to decide which combinations of letters are valid.
Data are stored in the file input.txt.
The first part of the data consists of the words in the dictionary in arbitrary order, one or more words per line. Assume each word is no longer than 10 letters. The number of words is unknown and this part of the data is terminated by the word $$$$.
Following the dictionary is a set of ‘digit’ strings, one per line. For each string, print all possible ‘dictionary’ words which can be formed from that string. This part of the data is terminated by 0.
All output must be sent to the file output.txt.
Marks will be awarded for appropriate choice of data structures and efficient algorithms.
You may assume that all data are valid.
Sample input
good
home
Gone
boy
any
hood
HOOF
help
yard
WARD
ware
BOX
BOW
cow
$$$$
4663
269
2345
4357
9273
0
Sample output
4663
Gone
good
home
hood
HOOF
269
any
BOW
BOX
boy
cow
2345
4357
help
9273
WARD
ware
yard
