1
$\begingroup$

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

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Richerby
    Commented May 5, 2016 at 5:12

1 Answer 1

Reset to default
1
$\begingroup$

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

Basically, this problem is trying to reveal your ability to solve problems using recursive algorithms/divide&conquer for generating all possible permutations (brute-force). There are some filtering techniques that can be used in practice, but the worst-case running time is exponential.

Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this?

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.

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) ?

These algorithms use DFS for its recursive nature. Probably, it uses BFS to avoid stackoverflow.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.