What’s The Number Again ?

In Algorithms, Graphs, Programming, Strings on September 16, 2010 at 9:49 pm
The previous post “What’s The Number” had a non-recursive implementation. Here is a recursive way of doing the same. It’s not as bad to have a recursive implementation as the max recursion depth is limited by the length of  a telephone number. If the input was longer / without an upper bound, recursion would be a bad move. This Recursive algorithm does a Depth First walk. A recursive Breadth First walk is much more painful to implement and has a higher memory overhead.
Given a telephone number like 4156434531, get all possible names that would match it.
e.g. If the number is 23, the names could be “ad”, “bd”, “cd”, “ae” etc..
public static class TelNumber
private static char[][] KeyChars = new char[10][];
static TelNumber()
KeyChars[0] = new char[]{‘+’};
KeyChars[1] = new char[]{‘ ‘};
KeyChars[2] = new char[]{‘a’,’b’,’c’};
KeyChars[3] = new char[]{‘d’,’e’,’f’};
KeyChars[4] = new char[]{‘g’,’h’,’i’};
public static void PrintCombination(StringBuffer prefix, int[] tel_no)
int index = prefix.Count;
if (index >= tel_no.Length)
foreach(char c in KeyChars[tel_no[index]])
PrintCombination(prefix, tel_no);

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

%d bloggers like this: