Example

solve(23)
// would return: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Use this image as a reference:

Courtesy of wikipedia

Courtesy of wikipedia

As you can see, from our example up above 2 maps to [a, b, c] and 3 maps to [d, e, f].

To calculate the possibilities you multiply the length of each array you’d have against each other. We have 2 arrays with length 3 so:

3 * 3 = 9

Okay, we got the possiblities. How do we actually solve this? Well, let’s just start with solving that one single case.

Get the maps together⌗

We need to first get the arrays together in a two dimensional array, this is easy to do. Convert the number to string, and run each through digit.

var keys = {
	2: ['a', 'b', 'c'],
	3: ['d', 'e', 'f'],
	// we'll add the rest later
};

function solve(num) {
	// this turns the number into a string
	var str = num.toString();
	var arr = [];
	// this loops over the single digits.
	for (var i = 0; i < str.length; i++) {
		arr.push(keys[Number(str[i])]);
	}
	console.log(arr);
}
// if you call it, it should print
// 0: ["a", "b", "c"]
// 1: ["d", "e", "f"]

Generate the combinations⌗

Aight, cool we got our arrays in a two-dimensional array. What’s next? Oh yeah, we wanna generate the possible patterns for our particular case(array with length 2).

var keys = {
	2: ['a', 'b', 'c'],
	3: ['d', 'e', 'f'],
};

function solve(num) {
	var str = num.toString();
	var arr = [];
	
	for (var i = 0; i < str.length; i++) {
		arr.push(keys[Number(str[i])]);
	}
	
	var one = arr[0];
	var two = arr[1];

	var combinations = [];
	
	// same as normal loop, x here is the index of value not the value itself
	for(var x in one) {
		for(var y in two) {
			// add our characters together to the array
			combinations.push(one[x]+two[y]);
		}
	}
	
	console.log(combinations)
}
// should print
// (9) ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

This is cool, but this only applies to one possible case. Which is two digit numbers, like 23 or 45. But not to digits bigger than two or less than two :(.

What do we do then? We’ll we can’t add more loops, cause that wouldn’t be dynamic. If we had 5 digits, we’d have 5 loops and that gets more complex the bigger the digits are.

Thankfully there is a better way to do this.

Modify the array in-place⌗

This means, the second item in the array should have the combination of the first item and the second item.

For example, say we want to calculate the combinations of 234. Our function should work like this:

/*
original array: [
	["a", "b", "c"], // 2
	["d", "e", "f"], // 3
	["g", "h", "i"], // 4
]

our modification: [
	["a", "b", "c"], // 2
	["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"], // 3
	["adg", "adh", "adi", "aeg", "aeh", "aei", "afg", "afh", "afi", "bdg", "bdh", "bdi", "beg", "beh", "bei", "bfg", "bfh", "bfi", "cdg", "cdh", "cdi", "ceg", "ceh", "cei", "cfg", "cfh", "cfi"] // 4
]
*/

So we combine two arrays together, and the second item becomes that combination. The whole process is idiomatic.

A javascript implementation would like this:

var keys = {
	2: ['a', 'b', 'c'],
	3: ['d', 'e', 'f'],
	4: ['g', 'h', 'i'],
};

function solve(num) {

	var str = num.toString();
	var arr = [];
	
	for (var i = 0; i < str.length; i++) {
		arr.push(keys[Number(str[i])]);
	}

	for(var i=0; i < arr.length-1; i++) {
		var combinations = [];

		var one = arr[i];
		var two = arr[i+1];
		
		for(var x in one) {
			for(var y in two) {
				combinations.push(one[x]+two[y]);
			}
		}
		
		arr[i+1] = combinations;
	}

	// return the last item in array
	return arr[arr.length-1]
}

and Voilà, the solution is dynamic.

I came by this problem originally from https://dailycodingproblem.com - They send you daily interview problems, so you could improve your algorithm skills…

If you a want a full-solution implemented in golang, checkout my github repo algo.