Letter Combinations of a Phone Number

Before iPhones, we had phones with keypads like this:

hci3-f6

Where each digit corresponds to a set of three or four letters.

Problem Description:

Write a program that, given a phone number, return all possible letter combinations that can be formed. Eg.

Given 23

The following letter combinations can be formed: “AD”, “AE”, “AF”, “BD”, “BE”, “BF”, “CD”, “CE”, “CF”.

Given 234

The following letter combinations can be formed:

“ADG”,”ADH”,”ADI”,”AEG”,”AEH”,”AEI”,”AFG”,

“AFH”,”AFI”,”BDG”,”BDH”,”BDI”,”BEG”,”BEH”,

“BEI”,”BFG”,”BFH”,”BFI”,”CDG”,”CDH”,”CDI”,

“CEG”,”CEH”,”CEI”,”CFG”,”CFH”,”CFI”.

Solution

This problem requires a complete search solution since we need to explore all possible letter combinations, more specifically we are gonna use a well known technique called BACKTRACKING (http://en.wikipedia.org/wiki/Backtracking), it is basically a recursive function that builds a tree “on the fly”, at each recursive call it gets the set of letters that corresponds to the current digit and calls itself recursively for every letter but now with the next digit as parameter.


 //Global variables
 StringBuilder tempSolution;
 ArrayList<String> result;
 String letters[];

 ArrayList<String> letterCombinations(String digits)
 {
     //Our map, we use the digit as an index to get the corresponding set of letters
     letters = new String[]{"", "", "ABC", "DEF", "GHI", "JKL", "MNO", "PQRS", "TUV", "WXYZ"};
     result = new ArrayList<String>();
     //tempSolution is used to build the solution on the fly
     tempSolution = new StringBuilder("");
     //here we call dfs function starting with digit at position zero
     backtracking(digits, 0);
     return result;
 }
 void backtracking(String digits, int i) // variable i points the current digit
 {
     //We get the set of corresponding letters for the current digit
     String setOfLetters = letters[digits.charAt(i) - 48];

     //Now we loop through the set of letters
     for(int a = 0; a < setOfLetters.length(); ++a)
     {
         //Append each one of the letters to our temporary solution
         tempSolution.append(setOfLetters.charAt(a));
         //have we finished?, if so, add this temporary combination to our resulting ArrayList
         if(i == digits.length() - 1)
             result.add(tempSolution.toString());
         else //otherwise call this function recursively but now with the next digit as current digit
             backtracking(digits, i + 1);

         //Here is where the magic of backtracking happens
         tempSolution.deleteCharAt(st.length() - 1);
     }
 }

It runs in O(3 ^ n), where n is the number of digits of the phone number.

Advertisements

One thought on “Letter Combinations of a Phone Number

  1. There is a mistake in the example solution, you are missing opposite combinations, DA, EA, FA … or mistake is only in a formulation of the problem.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s