During an interview I was asked how I would list every character conversion of a ten digit telephone number. I figured that at most there were 3^10 combinations, then he mentioned 9 has 4 characters, OK, so at most 4 to the 10'th. I said it could be done with a loop in loop process, but I'd probably use a recursive loop to do it. It's a phone interview, little hard to describe exactly how I'd do it and I'd just been presented the problem. Instead of 10 digits use a variable set of numbers (Kills loop in loop unless a lot more logic is added.) and you can't do recursive logic. So, a trick question, and I don't know the trick answer. OK, does anyone know the process for doing that? Can you come up with a better process than the one I came up with? (Including recursive) I haven't counted breaking up the numbers into words (breaking up into words with 0 or 1.) He did ask about recognizing words in the list of solutions. (A little beyond my skill level. He was OK with that.)
In the mean time, I wrote the recursive logic to handle digits from 1 to 19 numbers. A few numbers for the number of possible results:
3^10=59049, 4^10=1048576, (Oh yea, that'd be 2^20, no wonder that number was familiar.) 3^19=1162261467, 4^19=274877906944
I may or may not be able to handle 3^19 in memory, I'd rather not find out.
public static List<string> TeleWords(UInt64 telnum)
{
List<string> strlst = new List<string>();
if (telnum==0) return strlst;
string[] phon = {" "};
Dictionary<int, string> phones = new Dictionary<int, string>();
Dictionary<int, string[]> phone = new Dictionary<int, string[]>();
phone.Add(0, phon); phone.Add(1, phon);
phones.Add(2, "abc"); phones.Add(3, "def"); phones.Add(4, "ghi"); phones.Add(5, "jkl");
phones.Add(6, "mno"); phones.Add(7, "pqrs"); phones.Add(8, "tuv"); phones.Add(9, "wxyz");
foreach (int num in phones.Keys)
{
phon = new string[phones[num].Length];
for (int i = 0; i < phones[num].Length; i++)
phon[i] = phones[num].Substring(i, 1);
phone.Add(num, phon);
}
List<int> nums = new List<int>();
UInt64 tmx = telnum;
tmx /= 10;
tmx *= 10;
while (telnum > 0)
{
int ii = (int)(telnum - tmx);
nums.Add(ii);
telnum /= 10;
tmx /= 100;
tmx *= 10;
}
int x = nums.Count-1;
int[] lst = new int[nums.Count];
for (int i = 0; i <= x; i++)
lst[i] = nums[x - i];
TeleWords(strlst, 0, lst, new StringBuilder(), phone);
return strlst;
}
private static void TeleWords(List<string> strlst, int pos, int[] nmbrs, StringBuilder lst, Dictionary<int, string[]> phoneLtrs)
{
if (pos >= nmbrs.Length)
{
strlst.Add(lst.ToString());
return;
}
StringBuilder nlst = new StringBuilder();
int l = nmbrs.Length;
if (pos > 0) nlst.Append(lst.ToString());
foreach (string x in phoneLtrs[nmbrs[pos]])
{
nlst.Append(x);
TeleWords(strlst, pos + 1, nmbrs, nlst, phoneLtrs);
nlst.Remove(lst.Length, x.Length);
}
}