# Letter Combinations of a Phone Number

I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem).

Problem statement – Letter Combinations of a Phone Number

"Given a digit string, e.g., “23”, return all possible letter combinations that the number could represent. The mapping of digits to numbers is the same as on a telephone number pad. So for “23”, the combinations are, ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]."

There are plenty of solutions online and in books. However, I’m curious to know about the fundamentals of this problem.

Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this? Some solutions reference DFS and BFS. How are DFS and BFS related to this problem (are they possibly referring to the type of recursion being used to solve the problem) ?

Thanks

• I'm not sure there's really anything to say, here. Trivially, any algorithm has to take enough time to produce its output, and the output has length exponential in the number of digits in the phone number. So that gives an immediate lower bound on the efficiency of any algorithm that's going to solve the problem. Since the first algorithm you think of already has that complexity, that's basiically the end of the game. – David Richerby May 5 '16 at 5:12

Yes, one way to look at the problem is 'Cartesian product of multiple sets'. Given a string S, you can consider two sets a[i] and b[i], where a[i] is the set of character strings that can be made by substring S[1:i], and b[i] is the set of character strings that can be made by substring S[i+1,end]; then output the Cartesian product of a[i] and b[i] for every possible i. However, this algorithm is not the best one.
These algorithms use DFS for its recursive nature. Probably, it uses BFS to avoid stackoverflow.