Coding Quiz: Printing out all the possible letter combinations for a seven digit phone number
This is actually a slight variation on a question that I got asked at an interview: print out all possible letter combinations for a keypad.
I really wonder how one would solve this cold if you had never seen the problem ( or a variation on it) previously. What I outline here is a solution involving recursion; though there are versions that used nested loops; which are from intuitive.
I had gotten as far as setting up the dict and working on the recursion process ( which I had tried writing in perl before I learned that python is a far easier language to remember under pressure).
needless to say; its much easier to setup and test with a compiler.
Here is the process in main():
Setup the keypad dict: Use the digit values as the the keys and the letters on the keypad as values. I decided to keep an accurate phone mapping which has four letters for 8 and 9. I did though have the values for 0 (aka Operator) be 0 and 1 be 1. There are no character mappings for these values on phone. I have gotten into the habit of using characters as opposed to integers for keys; unless I have a precise need for the keys to have integer values.
Initialize Variables: Define the phone number and initialize the loop list.
Setup the loop list: This will be a list of character strings corresponding the phone number that will be used to determine the combinations.
Initialize the combo list: Set this equal to the character string that corresponds to the first digit in the phone number. In the example used; this is 'TUV'
Call the combo loop that returns the new combo list: I will detail that seperately.
Check/test the results: By printing out the list of all the combinations along with counting them. For the sake of this example; I picked numbers that all had three character mappings. Note that 3**7 =2187 which matches the count we get back.
Here is the process for combo(): Note that we pass in the loop and combo lists along with an integer level which is the digit that is be looked at or the current level of the recursion
initialize variables: the newcombo variable
Start the level loop: This will cycle through the loop variable for this level which is the character string of the current level ( or digit)
Start the combo loop (this is a nested loop): this will go through all the current values in the combo list.
Create the newcombo list: There are two operations going on at once: creation of the new string with the current character being added to the end of the current string. The result is then appended to the new combo list.
After both loops have finished:
Increment the level variable
conditional: If we still have more digits to look at
set combo equal to newcombo
call combo again ( noting that this time both combo and level are different)
return the newcombo variable back to main() once level equals 8
Here is the code and output:
https://gist.github.com/6350187