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