Telephone Number to Words - Permutation - C#


Keywords:c# 


Question: 

I was asked on an interview: Given a phone number, say 652-7872, print out all possible permutations of the words that it can spell.

2-ABC, 
3-DEF, 
4-GHI, 
5-JKL,
6-MNO,
7-PQRS,
8-TUV,
9-WXYZ,
0-O

For example, one permutation of 652-7872 is JGAJAPP.

I have seen similar questions answered, however, the solutions either aren't the letter individually OR the letters are random through out the whole string.

This question, I believe, is asking for

For position 0 of the phone number string (652-7872), 6 - the only possible letter options are "MNO"
For position 1 of the phone number string (652-7872), 5 - the only possible letter options are "JKL"
For position 2 of the phone number string (652-7872), 2 - the only possible letter options are "ABC"

A short version of possible outcomes for the first 3 #'s would be:

MJA
MJB
MJC
MKA
MKB
MKC
MLA
MLB
MLC

Would someone tell me how to solve this in C#? And I'd be interested in how long it takes you.


1 Answer: 

Here's what worked for me. Start with this:

var keys = new Dictionary<char, string>()
{
    { '1', "1" },
    { '2', "ABC" },
    { '3', "DEF" },
    { '4', "GHI" },
    { '5', "JKL" },
    { '6', "MNO" },
    { '7', "PQR" },
    { '8', "TUV" },
    { '9', "WXYZ" },
    { '0', "0" },
};

var number = "652";

Now I can define a recursive function to generate the permutations:

Func<
    IEnumerable<IEnumerable<char>>,
    IEnumerable<char>,
    IEnumerable<IEnumerable<char>>> f = null;
f = (css, cs) =>
{
    if (!cs.Any())
    {
        return css;
    }
    else
    {
        return f(css
            .SelectMany(
                x => keys[cs.First()],
                (x, k) => x.Concat(new [] { k })),
            cs.Skip(1));
    }
};

I can then call it this way:

var results =
    f(
        keys[number.ToCharArray().First()]
            .ToCharArray()
            .Select(x => new [] { x }),
        number.ToCharArray().Skip(1))
    .Select(x => new String(x.ToArray()));

I get these results:

results