LeetCode problem #17–Letter Combinations of a Phone Number (JavaScript)
In this LeetCode challenge we’re given a series of numbers in the form of digits on a phone keypad (0–9) and asked to produce every possible combination of letters that the numbers could create.
So in other words, given the number 2, our combinations are a, b and c. but given 23, our combinations are ad, ae, af, bd, be, bf, cd, ce and cf, and given the number 2546372 our combinations are… well you get the idea.
For all solutions, we need a map of digits to characters. There are a number of ways to present this, and the most concise is a 1-line option, but I’ve opted for readability in the solutions below.
Oh also, here’s a photo of a phone keypad, for you youngsters out there:
Solution #1: Triple loop
I know, I know, the concept of a triple loop makes you squirm and feel uncomfortable. However it is at least only a triple loop on small datasets.
The way this solution works is to first loop through the digits provided to the function. For each digit, we then loop through the possibilities found on the previous digit. Finally, we loop through the characters available for the current digit.
This series of loops allows us to add all available combinations for each digit, taking combinations for previous digits into account, and is almost exactly how you might process the question as a human.
Solution #2: Recursion
This solution isn’t all that different to the triple-loop one discussed above, but might be a little easier to read if you’re big on recursive functions.
What we do is that we take the digits passed in, find out all the possible combinations for the first digit, and then call the function again on the remaining digits. Each time, we pass in all combinations found so far, which means that by the end, we have an array of all possible combinations.