Write a recursive function named phoneWords that uses backtracking to print all seven-letter words that correspond to the digits of a given phone number.
On a standard telephone keypad, the letters A-Z are mapped onto the phone number digits 0-9 as shown in the following diagram.
A,B,C are mapped to 2, and D,E,F are mapped to 3, and so on.
Many businesses choose their phone numbers so that they can be read and written as words to make them easier to remember.
For example, 1-800-FLOWERS is really 1-800-356-9377.
The idea of this problem is that you will be given a seven-digit telephone number as a string, such as "3569377", along with a dictionary of seven-letter words, and you are to find and print all words that could be made using the seven digits of that phone number in their original order.
Your function will accept three parameters: a seven-letter string representing the 7-digit phone number; a reference to a Lexicon representing a dictionary; and a reference to a map from integers to strings, representing the phone number keypad mapping shown above at right.
The map's contents are always {2:"ABC", 3:"DEF", ..., 9:"WXYZ"}.
(This map is passed for convenience so that you don't need to write all of the code to do the number to character mapping.)
For example, if a standard English dictionary of 7-letter words is loaded into a Lexicon named dict, and the phone number mapping is called numberMap, then the call of phoneWords("3569377", dict, numberMap); should print:
FLOWERS
It turns out that "FLOWERS" is the only 7-letter word that corresponds to "3569377", but some phone numbers correspond to many words.
If this is the case, print all such words, one per line, in alphabetical order.
For example, the call of phoneWords("7874464", dict, numberMap); should print:
PURGING
PUSHING
RUSHING
SURGING
If no dictionary words correspond to the given phone number, you should not produce any output.
Assumptions: You may assume that the phone number passed will be exactly 7 characters in length, with no hyphens, area code, or other formatting in it.
All of the characters will be digits from '0' through '9'.
You may also assume that every word found in the dictionary is exactly 7 letters long, and that its words consist entirely of letters A-Z in uppercase.
Efficiency: Your code should avoid large areas of exploration that cannot lead to any solution. Specifically, if you are exploring the phone number "3569377" from our first example, and you have chosen to map the first three numbers "356" to the letters "FLM", there is no dictionary word that begins with those letters, so any further exploration cannot yield a working solution.
In such a case, your code should stop and backtrack immediately.
You should also avoid making lots of copies of large data structures by always passing them by reference.
Constraints:
- Do not modify the
Lexicon or map passed in to your function.
- Do not declare any global variables.
- You can use any data structures you like, and your code can contain loops, but the overall algorithm must be recursive and must use backtracking.
- You are allowed to define other "helper" functions if you like; they are subject to these same constraints.
