Letter Combinations of a Phone Number

Two years ago, during a FAANG coding interview, I was asked to print all the possible letter combinations of a phone number. I was shocked and I tried very hard during the interview but I gave up eventually. Today, I go over the question again and I finally know how to do it.

Let’s take a look at the question,

There are several things we need to know before we do the actual work.

1. Will there be a series of the same numbers in which the length is more than 4?
   yes, so for 22222, the result will be
   2 2 2 2 2-> AAAAA
   22 2 2 2-> BAAA
   2 22 2 2-> ABAA
   222 2 2-> CAA
   ……(and so on)
2. Does the input only contain numbers?
   yes, 0–9 only
3. If I get the input of 111111, the result will be an empty array?
   no, 1 means space, if you give me 111111, the function should return 6 spaces

How to do it?

The first thing comes up in my mind is to

1. split the input into a group of same numbers, such that, for input “222233442”, we will have [“22222”, “33”, “44”, ”2”]
2. and then we use recursion to get all the possibilities of combining “2”, “22” and “222” into “22222”. This is similar to the problem of Coin Change, finding all the combinations of coins which could come up with a certain amount.

3. finally, we can cross-combine the combinations from 2) into our result

compute
[
  [AAA, BA, AB, C], <- 222
  [D],              <- 3
]
into
[AAAD, BAD, ABD, CD]

Here is the complete snippet of my approach:

Previous:

A general approach to Subsets, Combinations and Permutations

I hope it helps

By the way, if you are interested in algorithms, here is my journey on a daily challenge, AlGoDaily. I have also included the above snippet in the repo, please feel free to new an issue/pull-request on it. Thank you.