Telephone Words

People often give others their telephone number as a word representing the seven-digit number. For example, if my telephone number were 866-2665, I could tell people my number is “TOOCOOL,” instead of the hard-to-remember seven-digit number. Note that many other possibilities (most of which are nonsensical) can represent 866-2665. You can see how letters correspond to numbers on a telephone keypad. Write a routine that takes a seven-digit telephone number and prints out all of the possible “words” or combinations of letters that can represent the given number. Because the 0 and 1 keys have no letters on them, you should change only the digits 2–9 to letters. You’ll be passed an array of seven integers, with each element being one digit in the number. You may assume that only valid phone numbers will be passed to your routine. You can use the helper routine char getCharKey( int telephoneKey, int place ) which takes a telephone key (0–9) and a place of either 1, 2, 3 and returns the character corresponding to the letter in that position on the specified key. For example, GetCharKey(3, 2) will return ‘E’ because the telephone key 3 has the letters “DEF” on it and ‘E’ is the second letter.

It’s worthwhile to define some terms for this problem. A telephone number consists of digits. Three letters correspond to each digit (except for 0 and 1, but when 0 and 1 are used in the context of creating a word, you can call them letters). The lowest letter, middle letter, and highest letter will be called the digit’s low value, middle value, and high value, respectively. You will be creating words, or strings of letters, to represent the given number.

First, impress the interviewer with your math skills by determining how many words can correspond to a seven-digit number. This requires combinatorial mathematics, but if you don’t remember this type of math, don’t panic. First, try a one-digit phone number. Clearly, this would have three words. Now, try a two-digit phone number - say, 56. There are three possibilities for the first letter, and for each of these there are three possibilities for the second letter. This yields a total of nine words that can correspond to this number. It appears that each additional digit increases the number of words by a factor of 3. Thus, for 7 digits, you have 3⁷ words, and for a phone number of length n, you have 3ⁿ words. Because 0 and 1 have no corresponding letters, a phone number with 0s or 1s in it would have fewer words, but 3⁷ is the upper bound on the number of words for a seven-digit number.

Now you need to figure out an algorithm for printing these words. Try writing out some words representing one of the author’s old college phone numbers, 497-1927, as an example. The most natural manner in which to list the words is alphabetical order. This way, you always know which word comes next and you are less likely to miss words. You know that there is on the order of 3⁷ words that can represent this number, so you won’t have time to write them all out. Try writing just the beginning and the end of the alphabetical sequence. You will probably want to start with the word that uses the low letter for each digit of the phone number. This guarantees that your first word is the first word in alphabetical order. Thus, the first word for 497-1927 becomes ‘G’ for 4 because 4 has “GHI” on it, ‘W’ for 9, which has “WXY” on it, ‘P’ for 7, which has “PRS” on it, and so on, resulting in “GWP1WAP”.

As you continue to write down words, you ultimately create a list that looks like the following:

GWP1WAP

GWP1WAR

GWP1WAS

GWP1WBP

GWP1WBR

…

IYS1YCR

IYS1YCS

It was easy to create this list because the algorithm for generating the words is relatively intuitive. Formalizing this algorithm is more challenging. A good place to start is by examining the process of going from one word to the next word in alphabetical order.

Because you know the first word in alphabetical order, determining how to get to the next word at any point gives you an algorithm for writing all the words. One important part of the process of going from one word to the next seems to be that the last letter always changes. It continually cycles through a pattern of P-R-S. Whenever the last letter goes from S back to P, it causes the next-to-last letter to change.

Try investigating this a little more to see if you can come up with specific rules. Again, it’s probably best to try an example. You may have to write down more words than in the example list to see a pattern (a three-digit phone number should be sufficient, or the previous list will work if it’s expanded a bit). It looks as if the following is always true: Whenever a letter changes, its right neighbor goes through all of its values before the original letter changes again. Conversely, whenever a letter resets to its low value, its left neighbor increases to the next value.

From these observations, there are probably two reasonable paths to follow as you search for the solution to this problem. You can start with the first letter and have a letter affect its right neighbor, or you can start with the last letter and have a letter affect its left neighbor. Both of these approaches seem reasonable, but you’ll have to choose one. For now, try the former and see where that gets you.

You should examine exactly what you’re trying to do at this point. You’re working with the observation that whenever a letter changes, it causes its right neighbor to cycle through all of its values before it changes again. You’re now using this observation to determine how to get from one word to the next word in alphabetical order. It may help to formalize this observation: Changing the letter in position i causes the letter in position i + 1 to cycle through its values. When you can write an algorithm in terms of how elements i and i + 1 interact with each other, it often indicates recursion, so try to figure out a recursive algorithm.

You have already discovered most of the algorithm. You know how each letter affects the next; you just need to figure out how to start the process and determine the base case. Looking again at the list to try to figure out the start condition, you’ll see that the first letter cycles only once. Therefore, if you start by cycling the first letter, this causes multiple cycles of the second letter, which causes multiple cycles of the third letter - exactly as desired. After you change the last letter, you can’t cycle anything else, so this is a good base case to end the recursion. When the base case occurs, you should also print out the word because you’ve just generated the next word in alphabetical order. The one special case you have to be aware of occurs when there is a 0 or 1 in the given telephone number. You don’t want to print out any word three times, so you should check for this case and cycle immediately if you encounter it.

In list form, the steps look like this:

If the current digit is past the last digit
   Print the word because you're at the end
Else
   For each of the three digits that can represent the current digit, going from
low to high
       Have the letter represent the current digit
       Move to next digit and recurse
       If the current digit is a 0 or a 1, return

The code is as follows:

static final int PHONE_NUMBER_LENGTH = 7;

void printTelephoneWords( int[] phoneNum ){
   char[] result = new char[ PHONE_NUMBER_LENGTH ];

   doPrintTelephoneWords( phoneNum, 0, result );

}

void doPrintTelephoneWords( int[] phoneNum, int curDigit,
                           char[] result ){
   if( curDigit == PHONE_NUMBER_LENGTH ){
     System.out.println( new String( result ) );
   return;
   }

   for( int i = 1; i <= 3; i++ ){
       result[ curDigit ] = getCharKey( phoneNum[curDigit], i );
       doPrintTelephoneWords( phoneNum, curDigit + 1, result );
       if( phoneNum[curDigit] == 0 ||
           phoneNum[curDigit] == 1) return;
   }
}

What is the running time of this algorithm? It can be no less than O(3ⁿ) because there are 3ⁿ solutions, so any correct solution must be at least O(3ⁿ). Getting each new word requires only constant time operations so the running time is indeed O(3ⁿ).

Important

Reimplement PrintTelephoneWords without using recursion.

The recursive algorithm doesn’t seem to be very helpful in this situation. Recursion was inherent in the way that you wrote out the steps of the algorithm. You could always try emulating recursion using a stack-based data structure, but there may be a better way involving a different algorithm. In the recursive solution, you solved the problem from left to right. You also made an observation that suggested the existence of another algorithm going from right to left: Whenever a letter changes from its high value to its low value, its left neighbor is incremented. Explore this observation and see if you can find a nonrecursive solution to the problem.

Again, you’re trying to figure out how to determine the next word in alphabetical order. Because you’re working from right to left, you should look for something that always happens on the right side of a word as it changes to the next word in alphabetical order. Looking back at the original observations, you noticed that the last letter always changes. This seems to indicate that a good way to start is to increment the last letter. If the last letter is at its high value and you increment it, you reset the last letter to its low value and increment the second-to-last letter. Suppose, however, that the second-to-last number is already at its high value. Try looking at the list to figure out what you need to do. From the list, it appears that you reset the second-to-last number to its low value and increment the third-to-last number. You continue carrying your increment like this until you don’t have to reset a letter to its low value.

This sounds like the algorithm you want, but you still have to work out how to start it and how to know when you’re finished. You can start by manually creating the first string as you did when writing out the list. Now you need to determine how to end. Look at the last string and figure out what happens if you try to increment it. Every letter resets to its low value. You could check whether every letter is at its low value, but this seems inefficient. The first letter resets only once, when you’ve printed out all of the words. You can use this to signal that you’re done printing out all of the words. Again, you have to consider the cases where there is a 0 or a 1. Because 0 and 1 effectively can’t be incremented (they always stay as 0 and 1), you should always treat a 0 or a 1 as if it were at its highest letter value and increment its left neighbor. In outline form, the steps are as follows:

Create the first word character by character
Loop infinitely:
    Print out the word
    Increment the last letter and carry the change
    If the first letter has reset, you're done

Here is the solution based on this sort of algorithm:

Tip

Note that you can cut down on the calls to getCharKey by storing each letter’s three values in variables, rather than making repeated calls to see whether a value is low, middle, or high. This makes the code a little more difficult, and this sort of optimization is probably unnecessary in the context of this solution.

static final int PHONE_NUMBER_LENGTH = 7;

void printTelephoneWords( int phoneNum[] ){
   char[] result = new char[ PHONE_NUMBER_LENGTH ];
   int i;

   /* Initialize the result (in our example,
    * put GWP1WAR in result).
    */
   for( i = 0; i < PHONE_NUMBER_LENGTH; i++ )
       result[i] = getCharKey( phoneNum[i], 1 );

   /* Main loop begins */
   while( true ){
       for( i = 0; i < PHONE_NUMBER_LENGTH; ++i ){
           System.out.print( result[i] );
       }
       System.out.print( '\n' );

       /* Start at the end and try to increment from right
        * to left.
        */
       for( i = PHONE_NUMBER_LENGTH - 1; i >= -1; i-- ){
           /* You're done because you
            * tried to carry the leftmost digit.
            */
           if( i == -1 ) return;

           /* Otherwise, we're not done and must continue. */

           /* You want to start with this condition so that you can
            * deal with the special cases, 0 and 1 right away.
            */
           if( getCharKey( phoneNum[i], 3 ) == result[i] ||
               phoneNum[i] == 0 || phoneNum[i] == 1 ){
               result[i] = getCharKey( phoneNum[i], 1 );
               /* No break, so loop continues to next digit */
           } else if ( getCharKey( phoneNum[i], 1 ) == result[i] ){
               result[i] = getCharKey( phoneNum[i], 2 );
               break;
           } else if ( getCharKey( phoneNum[i], 2 ) == result[i] ){
               result[i] = getCharKey( phoneNum[i], 3 );
               break;
           }
       }
   }
}

What’s the running time on this algorithm?

Again, there must be at least 3ⁿ solutions, so the algorithm can be no better than O(3ⁿ) if it is correct. There is slight constant overhead in finding each word, but you can ignore it. Therefore, this is also an O(3ⁿ) solution.