Friday, March 11, 2011

Given a telephone number print or produce all the possible telephone words or combinations of letters that can represent the given telephone number

import java.util.*;

class PhoneMmemonics
{

/**
* Mapping between a digit and the characters it represents
*/
private static Map> numberToCharacters = new
HashMap>();

static {
numberToCharacters.put('0',new ArrayList(Arrays.asList('0')));
numberToCharacters.put('1',new ArrayList(Arrays.asList('1')));
numberToCharacters.put('2',new ArrayList(Arrays.asList('A','B','C')));
numberToCharacters.put('3',new ArrayList(Arrays.asList('D','E','F')));
numberToCharacters.put('4',new ArrayList(Arrays.asList('G','H','I')));
numberToCharacters.put('5',new ArrayList(Arrays.asList('J','K','L')));
numberToCharacters.put('6',new ArrayList(Arrays.asList('M','N','O')));
numberToCharacters.put('7',new ArrayList(Arrays.asList('P','Q','R')));
numberToCharacters.put('8',new ArrayList(Arrays.asList('T','U','V')));
numberToCharacters.put('9',new ArrayList(Arrays.asList('W','X','Y','Z')));
}

/**
* Generates a list of all the mmemonics that can exists for the number
* @param phoneNumber
* @return
*/
public static List getMmemonics(int phoneNumber) {

// prepare results
StringBuilder stringBuffer = new StringBuilder();
List results = new ArrayList();

// generate all the mmenonics
generateMmemonics(Integer.toString(phoneNumber), stringBuffer, results);

// return results
return results;
}

/**
* Recursive helper method to generate all mmemonics
*
* @param partialPhoneNumber Numbers in the phone number that haven't converted to characters yet
* @param partialMmemonic The partial word that we have come up with so far
* @param results total list of all results of complete mmemonics
*/
private static void generateMmemonics(String partialPhoneNumber, StringBuilder partialMmemonic, List results) {

// are we there yet?
if (partialPhoneNumber.length() == 0) {

// base case: so add the mmemonic is complete
results.add(partialMmemonic.toString());
return;
}

// prepare variables for recursion
int currentPartialLength = partialMmemonic.length();
char firstNumber = partialPhoneNumber.charAt(0);
String remainingNumbers = partialPhoneNumber.substring(1);

// for each character that the single number represents
for(Character singleCharacter : numberToCharacters.get(firstNumber)) {

// append single character to our partial mmemonic so far
// and recurse down with the remaining characters
partialMmemonic.setLength(currentPartialLength);
generateMmemonics(remainingNumbers, partialMmemonic.append(singleCharacter), results);
}
}

public static void main(String a[])
{
List results = new ArrayList();
results=getMmemonics(23);

Iterator it=results.iterator();
while(it.hasNext())
{

System.out.println(it.next());
}

}

}


General Formula is Product of (nCr) where n ={0...9} & r={ 1,2,3};
if n=23

AD
AE
AF
BD
BE
BF
CD
CE
CF

3c1 * 3c1=9

for n=234

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

3c1*3c1*3c1=27

and so on


Another Method

class Program
{
static void Main(string[] args)
{
int[] phoneNumber = new int[]{2,3,4};
List telephoneWords = GetTelephoneWords(phoneNumber, 0);
}

//get all the combinations / telephone words for a given telephone number
static List GetTelephoneWords(int[] numbers, int index)
{
List newWords = new List();
if (index == numbers.Length - 1)
{
newWords.AddRange(GetLetters(numbers[index]));
}
else
{
List wordsSoFar = GetTelephoneWords(numbers, index + 1);
string[] letters = GetLetters(numbers[index]);

foreach (string letter in letters)
{
foreach (string oldWord in wordsSoFar)
{
newWords.Add(letter + oldWord);
}
}
}
return newWords;
}

//gets the letters corresponding to a telephone digit
static string[] GetLetters(int i)
{
switch (i)
{
case 1: return new string[]{"1"};
case 2: return new string[] { "a", "b", "c" };
case 3: return new string[] { "d", "e", "f" };
case 4: return new string[] { "g", "h", "i" };
case 5: return new string[] { "j", "k", "l" };
case 6: return new string[] { "m", "n", "o" };
case 7: return new string[] { "p", "q", "r", "s" };
case 8: return new string[] { "t", "u", "v" };
case 9: return new string[] { "w", "x", "y", "z" };
case 0: return new string[]{"0"};
default: return new string[] { };
}
}
}

No comments :