Before iPhones, we had phones with keypads like this:
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.
AlgorithmStuff 